# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
103015 |
2019-03-28T16:14:51 Z |
pavel |
Editor (BOI15_edi) |
C++14 |
|
877 ms |
228856 KB |
#include <cstdio>
#include <stack>
#include <set>
using namespace std;
typedef pair<int,int> ii;
const int MAXN = 1<<19;
struct node{
node *l, *r;
int x, w;
node(int v, int y=-1){
x=y;
w=v;
if(w>1){
l = new node(w/2, y);
r = new node(w/2, y);
}else{
l = r = nullptr;
}
}
node(const node& o){
x=o.x;w=o.w;l=o.l;r=o.r;
}
int query(int l1, int r1){
if(l1>=w || r1>=w || l1<0 || r1<0) return -1;
if(r1-l1+1==w) return x;
return max(l->query(l1, min(r1, w/2-1)), r->query(max(0, l1-w/2), r1-w/2));
}
node* change(int idx, int y){
if(w==1){
return new node(1, y);
}else{
node* nn = new node(*this);
if(idx<w/2) nn->l = l->change(idx, y);
else nn->r = r->change(idx-w/2, y);
nn->x=max(nn->l->x, nn->r->x);
return nn;
}
}
};
int n;
int b[MAXN];
node *seg;
node * st[MAXN];
int main(){
st[0]=new node(MAXN);
scanf("%d", &n);
for(int i=0;i<n;++i){
scanf("%d", &b[i]);
seg=st[i];
if(b[i]>0){
st[i+1]=seg->change(0, i);
}else{
int p = seg->query(0, -b[i]-1);
seg = st[p];
st[i+1] = seg->change(-b[i], i);
}
}
for(int i=1;i<=n;++i){
int k = st[i]->query(0, 0);
if(k==-1) puts("0");
else printf("%d\n", b[k]);
}
}
Compilation message
edi.cpp: In function 'int main()':
edi.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
edi.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &b[i]);
~~~~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
33144 KB |
Output is correct |
2 |
Correct |
61 ms |
36344 KB |
Output is correct |
3 |
Correct |
53 ms |
33116 KB |
Output is correct |
4 |
Correct |
53 ms |
33192 KB |
Output is correct |
5 |
Correct |
62 ms |
36472 KB |
Output is correct |
6 |
Correct |
60 ms |
33144 KB |
Output is correct |
7 |
Correct |
79 ms |
36344 KB |
Output is correct |
8 |
Correct |
57 ms |
33096 KB |
Output is correct |
9 |
Correct |
66 ms |
36344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
552 ms |
227920 KB |
Output is correct |
2 |
Correct |
564 ms |
228076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
422 ms |
130732 KB |
Output is correct |
2 |
Correct |
424 ms |
150176 KB |
Output is correct |
3 |
Correct |
490 ms |
188536 KB |
Output is correct |
4 |
Correct |
586 ms |
227964 KB |
Output is correct |
5 |
Correct |
819 ms |
228856 KB |
Output is correct |
6 |
Correct |
607 ms |
226064 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
33144 KB |
Output is correct |
2 |
Correct |
61 ms |
36344 KB |
Output is correct |
3 |
Correct |
53 ms |
33116 KB |
Output is correct |
4 |
Correct |
53 ms |
33192 KB |
Output is correct |
5 |
Correct |
62 ms |
36472 KB |
Output is correct |
6 |
Correct |
60 ms |
33144 KB |
Output is correct |
7 |
Correct |
79 ms |
36344 KB |
Output is correct |
8 |
Correct |
57 ms |
33096 KB |
Output is correct |
9 |
Correct |
66 ms |
36344 KB |
Output is correct |
10 |
Correct |
552 ms |
227920 KB |
Output is correct |
11 |
Correct |
564 ms |
228076 KB |
Output is correct |
12 |
Correct |
422 ms |
130732 KB |
Output is correct |
13 |
Correct |
424 ms |
150176 KB |
Output is correct |
14 |
Correct |
490 ms |
188536 KB |
Output is correct |
15 |
Correct |
586 ms |
227964 KB |
Output is correct |
16 |
Correct |
819 ms |
228856 KB |
Output is correct |
17 |
Correct |
607 ms |
226064 KB |
Output is correct |
18 |
Correct |
877 ms |
228568 KB |
Output is correct |
19 |
Correct |
609 ms |
228472 KB |
Output is correct |
20 |
Correct |
630 ms |
227236 KB |
Output is correct |
21 |
Correct |
559 ms |
228092 KB |
Output is correct |
22 |
Correct |
859 ms |
228856 KB |
Output is correct |