Submission #1441999
Source Code Expand
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
typedef long long ll;
const int NMAX = 1 << 18;
int N, n, dat[2*NMAX-1];
void init(int n_) {
n = 1;
while(n < n_) n *= 2;
FOR(i,0,2*n-1) dat[i] = 1e9;
}
void update(int k, int a) {
k += n - 1;
dat[k] = a;
while(k > 0) {
k = (k - 1) / 2;
dat[k] = min(dat[k*2+1],dat[k*2+2]);
}
}
int query(int a, int b, int k, int l, int r) {
if(r <= a || b <= l) return 1e9;
if(a <= l && r <= b) return dat[k];
else {
int vl = query(a,b,k*2+1,l,(l+r)/2);
int vr = query(a,b,k*2+2,(l+r)/2,r);
return min(vl, vr);
}
}
int mnidx[200005]; // 数字 - > インデックス
int dfs(int l, int r) {
if(r - l < 0) return 0;
int mn = query(l,r+1,0,0,n);
int i = mnidx[mn];
int ret = mn * (i - l + 1) * (r - i + 1);
ret += dfs(i+1,r);
ret += dfs(l,i-1);
return ret;
}
int main()
{
cin >> N;
init(N+10);
FOR(i,0,N+1) mnidx[i] = 0;
FOR(i,0,N) {
int a;
cin >> a;
mnidx[a] = i;
update(i,a);
}
cout << dfs(0,N-1) << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
B - Minimum Sum |
User |
nenuon |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
1382 Byte |
Status |
WA |
Exec Time |
141 ms |
Memory |
12416 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 400 |
Status |
|
|
Set Name |
Test Cases |
Sample |
example0, example1, example2 |
All |
corner0, corner1, corner2, corner3, example0, example1, example2, maxrand0, maxrand1, maxrand2, rand0, rand1, rand2 |
Case Name |
Status |
Exec Time |
Memory |
corner0 |
WA |
133 ms |
12416 KB |
corner1 |
WA |
116 ms |
3072 KB |
corner2 |
AC |
1 ms |
256 KB |
corner3 |
WA |
141 ms |
7808 KB |
example0 |
AC |
1 ms |
256 KB |
example1 |
AC |
1 ms |
256 KB |
example2 |
AC |
1 ms |
256 KB |
maxrand0 |
WA |
124 ms |
3072 KB |
maxrand1 |
WA |
126 ms |
3072 KB |
maxrand2 |
WA |
124 ms |
3072 KB |
rand0 |
AC |
1 ms |
256 KB |
rand1 |
AC |
1 ms |
256 KB |
rand2 |
AC |
1 ms |
256 KB |