#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);
^
# |
결과 |
실행 시간 |
메모리 |
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 |
3 ms |
8064 KB |
Output is correct |
8 |
Correct |
0 ms |
5556 KB |
Output is correct |
9 |
Correct |
3 ms |
8064 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
393 ms |
211872 KB |
Output is correct |
2 |
Correct |
333 ms |
211872 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
226 ms |
102312 KB |
Output is correct |
2 |
Correct |
279 ms |
122376 KB |
Output is correct |
3 |
Correct |
359 ms |
162372 KB |
Output is correct |
4 |
Correct |
359 ms |
211872 KB |
Output is correct |
5 |
Correct |
636 ms |
208308 KB |
Output is correct |
6 |
Correct |
349 ms |
211872 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
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 |
3 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 |
393 ms |
211872 KB |
Output is correct |
11 |
Correct |
333 ms |
211872 KB |
Output is correct |
12 |
Correct |
226 ms |
102312 KB |
Output is correct |
13 |
Correct |
279 ms |
122376 KB |
Output is correct |
14 |
Correct |
359 ms |
162372 KB |
Output is correct |
15 |
Correct |
359 ms |
211872 KB |
Output is correct |
16 |
Correct |
636 ms |
208308 KB |
Output is correct |
17 |
Correct |
349 ms |
211872 KB |
Output is correct |
18 |
Correct |
553 ms |
208308 KB |
Output is correct |
19 |
Correct |
396 ms |
208308 KB |
Output is correct |
20 |
Correct |
406 ms |
204876 KB |
Output is correct |
21 |
Correct |
369 ms |
211872 KB |
Output is correct |
22 |
Correct |
683 ms |
208308 KB |
Output is correct |