Submission #1354693

---

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,l,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]);
	}

	for(int i=1; i<=N; i++){
		where[a[i]] = i;
	}
	for(int i=1; i<=N; i++){
		if(where[i] == 0) return -1;
		if(seg[1] != i-1) return -1;
		tmp = -1;
		get(1,1,nn,1,where[i]-1);
		while(tmp < nn && tmp != -1){
			if(seg[tmp] <= 0) return -1;
			if(seg[tmp*2+1] != 0){
				tmp = tmp*2+1;
			}else tmp = tmp*2;
		}
		if(tmp == -1) left[i] = 1;
		else if(tmp >= nn) left[i] = tmp-nn+2;
		else return -1;
		tmp = -1;
		get2(1,1,nn,where[i]+1,N);
		while(tmp < nn && tmp != -1){
			if(seg[tmp] <= 0) return -1;
			if(seg[tmp*2] != 0){
				tmp = tmp*2;
			}else tmp = tmp*2+1;
		}
		if(tmp == -1) right[i] = N;
		else if(tmp >= nn) right[i] = tmp-nn;
		else return -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]) while(true);
		if(right[i] < where[i]) return -1;
	}
	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

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