#include<bits/stdc++.h>
using namespace std;
int N, a[300009], t[300009];
bool active[300009];
const int maxN = 15000009;
int nodes = 1, aint[maxN], l[maxN], r[maxN];
void build (int nod, int st, int dr)
{
aint[nod] = 0;
if (st == dr) return ;
int mij = (st + dr) >> 1;
l[nod] = ++nodes, build (l[nod], st, mij);
r[nod] = ++nodes, build (r[nod], mij + 1, dr);
}
void split (int nod)
{
if (l[nod] == 0)
l[nod] = ++nodes;
if (r[nod] == 0)
r[nod] = ++nodes;
if (aint[nod] > 0)
aint[l[nod]] = aint[r[nod]] = aint[nod],
aint[nod] = 0;
}
int change (int nod, int st, int dr, int x, int y, int newVal)
{
if (x <= st && dr <= y)
{
aint[++nodes] = newVal;
return nodes;
}
int mij = (st + dr) >> 1, curr = ++nodes;
split (nod);
if (x <= mij) l[curr] = change (l[nod], st, mij, x, y, newVal);
else l[curr] = l[nod];
if (mij < y) r[curr] = change (r[nod], mij + 1, dr, x, y, newVal);
else r[curr] = r[nod];
return curr;
}
int getPos (int nod, int st, int dr, int pos)
{
if (st == dr || aint[nod] > 0) return aint[nod];
int mij = (st + dr) >> 1;
split (nod);
if (pos <= mij) return getPos (l[nod], st, mij, pos);
return getPos (r[nod], mij + 1, dr, pos);
}
void print (int nod, int st, int dr)
{
if (st == dr)
{
if (st == 1) printf ("[");
printf ("%d ", aint[nod]);
if (dr == N) printf ("]\n");
return ;
}
int mij = (st + dr) >> 1;
split (nod);
print (l[nod], st, mij);
print (r[nod], mij + 1, dr);
}
set < int > S;
int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);
scanf ("%d", &N);
build (1, 1, N), r[0] = 1;
for (int i=1; i<=N; i++)
{
scanf ("%d", &a[i]);
if (a[i] < 0)
{
int deg = -a[i], K = getPos (r[i - 1], 1, N, deg);
if (!S.empty () && K < (*S.rbegin ())) t[i] = *S.rbegin (), K = i;
else t[i] = t[K];
r[i] = change (r[K - 1], 1, N, deg + 1, N, i);
if (active[t[i]]) S.erase (t[i]), active[t[i]] = 0;
else active[t[i]] = 1, S.insert (t[i]);
}
else r[i] = r[i - 1], S.insert (i), active[i] = 1;
//print (r[i], 1, N);
if (!S.empty ()) printf ("%d\n", a[*S.rbegin ()]);
else printf ("0\n");
}
return 0;
}
Compilation message
edi.cpp: In function 'int main()':
edi.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", &N);
~~~~~~^~~~~~~~~~
edi.cpp:80:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", &a[i]);
~~~~~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
6 ms |
1712 KB |
Output is correct |
3 |
Correct |
2 ms |
1712 KB |
Output is correct |
4 |
Correct |
2 ms |
1712 KB |
Output is correct |
5 |
Correct |
6 ms |
1972 KB |
Output is correct |
6 |
Correct |
2 ms |
1972 KB |
Output is correct |
7 |
Correct |
5 ms |
1972 KB |
Output is correct |
8 |
Correct |
2 ms |
1972 KB |
Output is correct |
9 |
Correct |
7 ms |
1972 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
271 ms |
79232 KB |
Output is correct |
2 |
Correct |
253 ms |
79232 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
165 ms |
79232 KB |
Output is correct |
2 |
Correct |
179 ms |
79232 KB |
Output is correct |
3 |
Correct |
235 ms |
88888 KB |
Output is correct |
4 |
Correct |
224 ms |
88888 KB |
Output is correct |
5 |
Correct |
328 ms |
111048 KB |
Output is correct |
6 |
Correct |
179 ms |
111048 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
6 ms |
1712 KB |
Output is correct |
3 |
Correct |
2 ms |
1712 KB |
Output is correct |
4 |
Correct |
2 ms |
1712 KB |
Output is correct |
5 |
Correct |
6 ms |
1972 KB |
Output is correct |
6 |
Correct |
2 ms |
1972 KB |
Output is correct |
7 |
Correct |
5 ms |
1972 KB |
Output is correct |
8 |
Correct |
2 ms |
1972 KB |
Output is correct |
9 |
Correct |
7 ms |
1972 KB |
Output is correct |
10 |
Correct |
271 ms |
79232 KB |
Output is correct |
11 |
Correct |
253 ms |
79232 KB |
Output is correct |
12 |
Correct |
165 ms |
79232 KB |
Output is correct |
13 |
Correct |
179 ms |
79232 KB |
Output is correct |
14 |
Correct |
235 ms |
88888 KB |
Output is correct |
15 |
Correct |
224 ms |
88888 KB |
Output is correct |
16 |
Correct |
328 ms |
111048 KB |
Output is correct |
17 |
Correct |
179 ms |
111048 KB |
Output is correct |
18 |
Correct |
350 ms |
112288 KB |
Output is correct |
19 |
Correct |
289 ms |
112288 KB |
Output is correct |
20 |
Correct |
294 ms |
117056 KB |
Output is correct |
21 |
Correct |
225 ms |
117056 KB |
Output is correct |
22 |
Correct |
321 ms |
118308 KB |
Output is correct |