# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
27036 |
2017-07-09T05:51:49 Z |
김현수(#1118) |
Editor (BOI15_edi) |
C++14 |
|
703 ms |
211872 KB |
#include<bits/stdc++.h>
using namespace std;
const int N = 300005;
int n, a[N];
struct node {
int v; node *lc, *rc;
node () {v=0; lc=NULL; rc=NULL;}
void init (int L=0, int R=n) {
if(L == R) return;
int M = (L+R)/2;
lc = new node(); lc->init(L, M);
rc = new node(); rc->init(M+1, R);
}
void upd (node *Q, int P, int V, int L=0, int R=n) {
if(L == R) {v = max(Q->v, V); return;}
int M = (L+R)/2;
if(P <= M) {
rc = Q->rc; lc = new node();
lc->upd(Q->lc, P, V, L, M);
}
else {
lc = Q->lc; rc = new node();
rc->upd(Q->rc, P, V, M+1, R);
}
v = max(lc->v, rc->v);
}
int get (int S, int E, int L=0, int R=n) {
if(S <= L && R <= E) return v;
if(E < L || R < S) return 0;
int T = 0, M = (L+R)/2;
if(lc) T = max(T, lc->get(S, E, L, M));
if(rc) T = max(T, rc->get(S, E, M+1, R));
return T;
}
} *rt[N];
int main()
{
scanf("%d",&n);
rt[0] = new node();
rt[0]->init();
for(int i=1;i<=n;i++) {
int T; scanf("%d",&T);
rt[i] = new node();
if(T < 0) {
int I = rt[i-1]->get(0, -T-1);
rt[i]->upd(rt[I-1], -T, i);
a[i] = a[I-1];
}
else {
rt[i]->upd(rt[i-1], 0, i);
a[i] = T;
}
printf("%d\n",a[i]);
}
}
Compilation message
edi.cpp: In function 'int main()':
edi.cpp:41:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
edi.cpp:45:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int T; scanf("%d",&T);
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
5556 KB |
Output is correct |
2 |
Correct |
0 ms |
8064 KB |
Output is correct |
3 |
Correct |
0 ms |
5556 KB |
Output is correct |
4 |
Correct |
0 ms |
5556 KB |
Output is correct |
5 |
Correct |
6 ms |
7932 KB |
Output is correct |
6 |
Correct |
0 ms |
5556 KB |
Output is correct |
7 |
Correct |
6 ms |
8064 KB |
Output is correct |
8 |
Correct |
0 ms |
5556 KB |
Output is correct |
9 |
Correct |
3 ms |
8064 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
359 ms |
211872 KB |
Output is correct |
2 |
Correct |
299 ms |
211872 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
186 ms |
102312 KB |
Output is correct |
2 |
Correct |
246 ms |
122376 KB |
Output is correct |
3 |
Correct |
323 ms |
162372 KB |
Output is correct |
4 |
Correct |
363 ms |
211872 KB |
Output is correct |
5 |
Correct |
619 ms |
208308 KB |
Output is correct |
6 |
Correct |
346 ms |
211872 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
5556 KB |
Output is correct |
2 |
Correct |
0 ms |
8064 KB |
Output is correct |
3 |
Correct |
0 ms |
5556 KB |
Output is correct |
4 |
Correct |
0 ms |
5556 KB |
Output is correct |
5 |
Correct |
6 ms |
7932 KB |
Output is correct |
6 |
Correct |
0 ms |
5556 KB |
Output is correct |
7 |
Correct |
6 ms |
8064 KB |
Output is correct |
8 |
Correct |
0 ms |
5556 KB |
Output is correct |
9 |
Correct |
3 ms |
8064 KB |
Output is correct |
10 |
Correct |
359 ms |
211872 KB |
Output is correct |
11 |
Correct |
299 ms |
211872 KB |
Output is correct |
12 |
Correct |
186 ms |
102312 KB |
Output is correct |
13 |
Correct |
246 ms |
122376 KB |
Output is correct |
14 |
Correct |
323 ms |
162372 KB |
Output is correct |
15 |
Correct |
363 ms |
211872 KB |
Output is correct |
16 |
Correct |
619 ms |
208308 KB |
Output is correct |
17 |
Correct |
346 ms |
211872 KB |
Output is correct |
18 |
Correct |
549 ms |
208308 KB |
Output is correct |
19 |
Correct |
473 ms |
208308 KB |
Output is correct |
20 |
Correct |
466 ms |
204876 KB |
Output is correct |
21 |
Correct |
393 ms |
211872 KB |
Output is correct |
22 |
Correct |
703 ms |
208308 KB |
Output is correct |