Submission #134763

#	Time	Username	Problem	Language	Result	Execution time	Memory
134763		Ace	Editor (BOI15_edi)	C++14	100 / 100	272 ms	57308 KiB

edi

#include<bits/stdc++.h>
using namespace std;

const int N = 3e5;

int n;
int ans[N+5];
int mini[N+5][22];
int par[N+5][22];

void make_spar(int x){
	for(int j=1;j<=20;j++){
		par[x][j] = par[par[x][j-1]][j-1];
		mini[x][j] = min(mini[x][j-1],mini[par[x][j-1]][j-1]);
	}
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		if(x>0){
			ans[i] = x;
			par[i][0] = i;
			continue;
		}
		x*=-1;
		int cur = i-1;
		for(int j=20;j>=0;j--){
			if(mini[cur][j] < x){ //valid
				continue;
			}
			cur = par[cur][j];
		}
		par[i][0] = cur-1;
		ans[i] = ans[par[i][0]];
		mini[i][0] = x;
		make_spar(i);
	}
	for(int i=1;i<=n;i++){
		printf("%d\n",ans[i]);
	}
	return 0;
}

Compilation message (stderr)

edi.cpp: In function 'int main()':
edi.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
edi.cpp:22:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&x);
   ~~~~~^~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 15 / 15
• Subtask 3: 28 / 28
• Subtask 4: 37 / 37