#include <bits/stdc++.h>
//#ifdef atom #else #endif
using namespace std;
typedef long long ll; typedef pair<int, int> ii;
#define X first
#define Y second
#define vi vector<int>
#define vii vector< ii >
#define pb push_back
int n;
struct node
{
int v;
node *left, *right;
node(int _v, node *a, node *b)
{
v = _v;
left = a; right = b;
}
node *insert(int x, int dx, int L = 0, int R = n)
{
if(L<= x && x<= R)
{
if(L == R) return new node(dx, NULL, NULL);
int M = (L+R)/2;
node *ret = new node(0, left->insert(x, dx, L, M), right->insert(x, dx, M+1, R));
ret->v = max(ret->left->v, ret->right->v);
//printf("L R is %d\n", ret->v);
return ret;
}
return this;
}
int ask(int i, int j, int L = 0, int R = n)
{
if(i> R || j< L) return 0;
if(i<= L && R<= j) return v;
int M = (L+R)/2;
int x = left->ask(i, j, L, M);
int y = right->ask(i, j, M+1, R);
return max(x, y);
}
};
const int maxn = 3e5+5;
node *root[maxn];
int num[maxn];
node *zero;
int main()
{
//#ifndef atom freopen(".in", "r", stdin); freopen(".out", "w", stdout); #endif
cin >> n;
zero = new node(0, NULL, NULL);
zero->left = zero->right = zero;
root[0] = zero;
for(int i = 1; i<= n; i++)
{
int x; scanf("%d", &x);
if(x> 0)
{
root[i] = root[i-1]->insert(0, i);
num[i] = x;
}
else
{
x = -x;
int det = root[i-1]->ask(0, x-1);
det--;
//printf("from (%d)\n", det);
root[i] = root[det]->insert(x, i);
//printf("max is %d\n", root[i]->ask(0, 1));
}
printf("%d\n", num[root[i]->ask(0, 0)]);
//cout << num[root[i]->ask(0, 0)] << endl;
}
}
Compilation message
edi.cpp: In function 'int main()':
edi.cpp:56:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int x; scanf("%d", &x);
~~~~~^~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
8 ms |
2552 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
8 ms |
2424 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
8 ms |
2680 KB |
Output is correct |
8 |
Correct |
2 ms |
380 KB |
Output is correct |
9 |
Correct |
8 ms |
2552 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
482 ms |
195124 KB |
Output is correct |
2 |
Correct |
484 ms |
195124 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
243 ms |
91128 KB |
Output is correct |
2 |
Correct |
284 ms |
110072 KB |
Output is correct |
3 |
Correct |
413 ms |
146380 KB |
Output is correct |
4 |
Correct |
481 ms |
195184 KB |
Output is correct |
5 |
Correct |
593 ms |
192248 KB |
Output is correct |
6 |
Correct |
463 ms |
193020 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
8 ms |
2552 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
8 ms |
2424 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
8 ms |
2680 KB |
Output is correct |
8 |
Correct |
2 ms |
380 KB |
Output is correct |
9 |
Correct |
8 ms |
2552 KB |
Output is correct |
10 |
Correct |
482 ms |
195124 KB |
Output is correct |
11 |
Correct |
484 ms |
195124 KB |
Output is correct |
12 |
Correct |
243 ms |
91128 KB |
Output is correct |
13 |
Correct |
284 ms |
110072 KB |
Output is correct |
14 |
Correct |
413 ms |
146380 KB |
Output is correct |
15 |
Correct |
481 ms |
195184 KB |
Output is correct |
16 |
Correct |
593 ms |
192248 KB |
Output is correct |
17 |
Correct |
463 ms |
193020 KB |
Output is correct |
18 |
Correct |
511 ms |
191580 KB |
Output is correct |
19 |
Correct |
495 ms |
191736 KB |
Output is correct |
20 |
Correct |
521 ms |
186232 KB |
Output is correct |
21 |
Correct |
484 ms |
195312 KB |
Output is correct |
22 |
Correct |
644 ms |
192292 KB |
Output is correct |