oj.uz

Submission #134763

# Submission time Handle Problem Language Result Execution time Memory
134763 2019-07-23T08:56:39 Z Ace Editor (BOI15_edi) C++14
100 / 100
 272 ms 57308 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 1016 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 5 ms 1272 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 4 ms 1272 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 5 ms 1272 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 56612 KB Output is correct
2 Correct 140 ms 56568 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 22164 KB Output is correct
2 Correct 78 ms 26468 KB Output is correct
3 Correct 217 ms 44792 KB Output is correct
4 Correct 140 ms 56696 KB Output is correct
5 Correct 147 ms 57308 KB Output is correct
6 Correct 182 ms 54576 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 1016 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 5 ms 1272 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 4 ms 1272 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 5 ms 1272 KB Output is correct
10 Correct 149 ms 56612 KB Output is correct
11 Correct 140 ms 56568 KB Output is correct
12 Correct 64 ms 22164 KB Output is correct
13 Correct 78 ms 26468 KB Output is correct
14 Correct 217 ms 44792 KB Output is correct
15 Correct 140 ms 56696 KB Output is correct
16 Correct 147 ms 57308 KB Output is correct
17 Correct 182 ms 54576 KB Output is correct
18 Correct 127 ms 44296 KB Output is correct
19 Correct 133 ms 44152 KB Output is correct
20 Correct 272 ms 55808 KB Output is correct
21 Correct 140 ms 56568 KB Output is correct
22 Correct 147 ms 57208 KB Output is correct