#include <bits/stdc++.h>
using namespace std;
const int mx = 3e5+5;
int n, ans[mx], up[mx][19], mn[mx][19];
int main(){
cin >> n;
for (int i = 1; i <= n; i++){
int a; cin >> a; if (a > 0){ ans[i] = a; continue; }
a *= -1; int pos = i-1;
for (int l = 18; l >= 0; l--) if (mn[pos][l] >= a) pos = up[pos][l];
up[i][0] = pos-1, mn[i][0] = a, ans[i] = ans[pos-1];
for (int l = 1; l < 18; l++){
up[i][l] = up[up[i][l-1]][l-1];
mn[i][l] = min(mn[i][l-1], mn[up[i][l-1]][l-1]);
}
}for (int i = 1; i <= n; i++) cout<<ans[i]<<endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
10 ms |
748 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
11 ms |
1100 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
10 ms |
1116 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
11 ms |
1100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
613 ms |
49444 KB |
Output is correct |
2 |
Correct |
609 ms |
49472 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
301 ms |
13892 KB |
Output is correct |
2 |
Correct |
359 ms |
16608 KB |
Output is correct |
3 |
Correct |
603 ms |
39108 KB |
Output is correct |
4 |
Correct |
606 ms |
49376 KB |
Output is correct |
5 |
Correct |
629 ms |
50120 KB |
Output is correct |
6 |
Correct |
618 ms |
47680 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
10 ms |
748 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
11 ms |
1100 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
10 ms |
1116 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
11 ms |
1100 KB |
Output is correct |
10 |
Correct |
613 ms |
49444 KB |
Output is correct |
11 |
Correct |
609 ms |
49472 KB |
Output is correct |
12 |
Correct |
301 ms |
13892 KB |
Output is correct |
13 |
Correct |
359 ms |
16608 KB |
Output is correct |
14 |
Correct |
603 ms |
39108 KB |
Output is correct |
15 |
Correct |
606 ms |
49376 KB |
Output is correct |
16 |
Correct |
629 ms |
50120 KB |
Output is correct |
17 |
Correct |
618 ms |
47680 KB |
Output is correct |
18 |
Correct |
629 ms |
27708 KB |
Output is correct |
19 |
Correct |
614 ms |
27772 KB |
Output is correct |
20 |
Correct |
754 ms |
48576 KB |
Output is correct |
21 |
Correct |
609 ms |
49476 KB |
Output is correct |
22 |
Correct |
632 ms |
50324 KB |
Output is correct |