# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
27092 |
2017-07-09T08:30:48 Z |
tlwpdus |
Editor (BOI15_edi) |
C++ |
|
896 ms |
399308 KB |
#include <bits/stdc++.h>
using namespace std;
int n;
struct node {
node *l, *r;
int val;
node() {val = 0; l = r = NULL;}
node(int v):val(v){l = r = NULL;}
void init(int s = 0, int e = n) {
if (s==e) return;
int m = (s+e)>>1;
if (!l) l = new node();
if (!r) r = new node();
l->init(s,m); r->init(m+1,e);
val = max(l->val,r->val);
}
int getv(int S, int E, int s = 0, int e = n) {
if (e<S||E<s) return 0;
if (S<=s&&e<=E) return val;
int m = (s+e)>>1;
return max(l->getv(S,E,s,m),r->getv(S,E,m+1,e));
}
node* upd(int idx, int val, node *ori, int s = 0, int e = n) {
if (e<idx||idx<s) return ori;
if (s==e) return new node(val);
int m = (s+e)>>1;
if (!l) l = new node();
l = l->upd(idx,val,ori->l,s,m);
if (!r) r = new node();
r = r->upd(idx,val,ori->r,m+1,e);
this->val = max(l->val,r->val);
return this;
}
} *head[300100];
int arr[300100];
int main() {
int i;
scanf("%d",&n);
head[0] = new node();
head[0]->init();
for (i=1;i<=n;i++) {
head[i] = new node();
scanf("%d",&arr[i]);
if (arr[i]>0) {
head[i] = head[i]->upd(0,i,head[0]);
}
else {
arr[i] *= -1;
head[i] = head[i]->upd(arr[i],i,head[head[i-1]->getv(0,arr[i]-1)-1]);
}
printf("%d\n",arr[head[i]->getv(0,0)]);
}
return 0;
}
Compilation message
edi.cpp: In function 'int main()':
edi.cpp:43:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
edi.cpp:48:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&arr[i]);
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
5552 KB |
Output is correct |
2 |
Correct |
6 ms |
10172 KB |
Output is correct |
3 |
Correct |
0 ms |
5552 KB |
Output is correct |
4 |
Correct |
0 ms |
5552 KB |
Output is correct |
5 |
Correct |
6 ms |
10040 KB |
Output is correct |
6 |
Correct |
0 ms |
5552 KB |
Output is correct |
7 |
Correct |
13 ms |
10304 KB |
Output is correct |
8 |
Correct |
0 ms |
5552 KB |
Output is correct |
9 |
Correct |
9 ms |
10172 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
613 ms |
399308 KB |
Output is correct |
2 |
Correct |
626 ms |
399308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
456 ms |
189560 KB |
Output is correct |
2 |
Correct |
469 ms |
227972 KB |
Output is correct |
3 |
Correct |
513 ms |
304136 KB |
Output is correct |
4 |
Correct |
616 ms |
399308 KB |
Output is correct |
5 |
Correct |
803 ms |
392312 KB |
Output is correct |
6 |
Correct |
626 ms |
399308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
5552 KB |
Output is correct |
2 |
Correct |
6 ms |
10172 KB |
Output is correct |
3 |
Correct |
0 ms |
5552 KB |
Output is correct |
4 |
Correct |
0 ms |
5552 KB |
Output is correct |
5 |
Correct |
6 ms |
10040 KB |
Output is correct |
6 |
Correct |
0 ms |
5552 KB |
Output is correct |
7 |
Correct |
13 ms |
10304 KB |
Output is correct |
8 |
Correct |
0 ms |
5552 KB |
Output is correct |
9 |
Correct |
9 ms |
10172 KB |
Output is correct |
10 |
Correct |
613 ms |
399308 KB |
Output is correct |
11 |
Correct |
626 ms |
399308 KB |
Output is correct |
12 |
Correct |
456 ms |
189560 KB |
Output is correct |
13 |
Correct |
469 ms |
227972 KB |
Output is correct |
14 |
Correct |
513 ms |
304136 KB |
Output is correct |
15 |
Correct |
616 ms |
399308 KB |
Output is correct |
16 |
Correct |
803 ms |
392312 KB |
Output is correct |
17 |
Correct |
626 ms |
399308 KB |
Output is correct |
18 |
Correct |
896 ms |
392312 KB |
Output is correct |
19 |
Correct |
886 ms |
392312 KB |
Output is correct |
20 |
Correct |
663 ms |
385316 KB |
Output is correct |
21 |
Correct |
679 ms |
399308 KB |
Output is correct |
22 |
Correct |
849 ms |
392312 KB |
Output is correct |