Submission #1354663


Source Code Expand

#include <bits/stdc++.h>

#define pb push_back
#define left lleft
#define right rright
#define lld long long

using namespace std;

int N,nn; lld ans;
int a[200002]; lld where[200002];
lld left[200002],right[200002];
int seg[600002];

int tmp;
void get(int node,int l,int r,int s,int e){
	if(r < s || e < l || s > e || seg[node] == 0) return;
	if(s <= l && r <= e){
		tmp = node;
		return;
	}
	int mid = (l+r)/2;
	get(node*2,1,mid,s,e);
	get(node*2+1,mid+1,r,s,e);
}
void get2(int node,int l,int r,int s,int e){
	if(r < s || e < l || s > e || seg[node] == 0) return;
	if(s <= l && r <= e){
		tmp = node;
		return;
	}
	int mid = (l+r)/2;
	get2(node*2+1,mid+1,r,s,e);
	get2(node*2,l,mid,s,e);
}

int main(){
	scanf("%d",&N);
	for(nn=1; nn<N; nn*=2);
	if(N > 200000) while(true);
	for(int i=1; i<=N; i++){
		scanf("%d",&a[i]);
		where[a[i]] = i;
	}
	for(int i=1; i<=N; i++){
		tmp = -1;
		get(1,1,nn,1,where[i]-1);
		while(tmp < nn && tmp != -1){
			if(seg[tmp*2+1] != 0){
				tmp = tmp*2+1;
			}else tmp = tmp*2;
		}
		if(tmp == -1) left[i] = nn;
		else left[i] = tmp+1;
		tmp = -1;
		get2(1,1,nn,where[i]+1,N);
		while(tmp < nn && tmp != -1){
			if(seg[tmp*2] != 0){
				tmp = tmp*2;
			}else tmp = tmp*2+1;
		}
		if(tmp == -1) right[i] = nn+N-1;
		else right[i] = tmp-1;
		left[i] -= (nn-1); right[i] -= (nn-1);
		int x = nn+where[i]-1;
		if(x < nn || x > nn+N-1) while(true);
		while(x > 0){
			if(x < 1 || x > 600000) while(true);
			seg[x]++;
			x /= 2;
		}
		//if(left[i] > where[i] || right[i] < where[i]) while(true);
	}
	for(int i=1; i<=N; i++){
		ans += ((right[i]-where[i]+1)*(where[i]-left[i]+1)*(lld)i);
		//printf("%lld %lld\n",left[i],right[i]);
	}
	printf("%lld\n",ans);

	return 0;
}

Submission Info

Submission Time
Task B - Minimum Sum
User suhgyuho
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1778 Byte
Status RE
Exec Time 186 ms
Memory 7552 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:38:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&N);
                ^
./Main.cpp:42:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);
                    ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 400
Status
AC × 3
AC × 6
WA × 4
RE × 3
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 AC 59 ms 7552 KB
corner1 WA 81 ms 7552 KB
corner2 AC 2 ms 4352 KB
corner3 WA 80 ms 7552 KB
example0 AC 2 ms 4352 KB
example1 AC 2 ms 4352 KB
example2 AC 2 ms 4352 KB
maxrand0 RE 186 ms 7552 KB
maxrand1 RE 183 ms 7552 KB
maxrand2 RE 182 ms 7552 KB
rand0 WA 2 ms 4352 KB
rand1 AC 2 ms 4352 KB
rand2 WA 2 ms 4352 KB