| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 502280 |
2022-01-05T17:03:02 Z |
rk42745417 |
Editor (BOI15_edi) |
C++17 |
|
108 ms |
50152 KB |
#include <bits/stdc++.h>
using namespace std;
#define EMiliaMyWife ios::sync_with_stdio(0); cin.tie(0);
using ll = int64_t;
using ull = uint64_t;
using uint = uint32_t;
using ld = long double;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const ll LINF = ll(2e18) + ll(1e15);
const double EPS = 1e-8;
static auto LamyIsCute = []() {
EMiliaMyWife
return 48763;
}();
const int N = 3e5 + 25, LGN = 19;
int anc[LGN][N], mn[LGN][N], state[N];
signed main() {
int n;
cin >> n;
for(int i = 1; i <= n; i++) {
int x;
cin >> x;
x = -x;
if(x > 0) {
int r = i - 1;
for(int j = LGN - 1; ~j; j--)
if(mn[j][r] >= x)
r = anc[j][r];
assert(r > 0);
anc[0][i] = r - 1;
mn[0][i] = x;
}
else {
state[i] = -x;
anc[0][i] = i;
}
for(int j = 1; j < LGN; j++) {
anc[j][i] = anc[j - 1][anc[j - 1][i]];
mn[j][i] = min(mn[j - 1][i], mn[j - 1][anc[j - 1][i]]);
}
cout << state[anc[LGN - 1][i]] << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
460 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1356 KB |
Output is correct |
| 3 |
Correct |
1 ms |
460 KB |
Output is correct |
| 4 |
Correct |
1 ms |
460 KB |
Output is correct |
| 5 |
Correct |
2 ms |
1356 KB |
Output is correct |
| 6 |
Correct |
1 ms |
460 KB |
Output is correct |
| 7 |
Correct |
3 ms |
1356 KB |
Output is correct |
| 8 |
Correct |
0 ms |
460 KB |
Output is correct |
| 9 |
Correct |
2 ms |
1356 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
103 ms |
49476 KB |
Output is correct |
| 2 |
Correct |
86 ms |
49512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
47 ms |
24484 KB |
Output is correct |
| 2 |
Correct |
54 ms |
29332 KB |
Output is correct |
| 3 |
Correct |
93 ms |
38256 KB |
Output is correct |
| 4 |
Correct |
84 ms |
49476 KB |
Output is correct |
| 5 |
Correct |
93 ms |
50092 KB |
Output is correct |
| 6 |
Correct |
77 ms |
47432 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
460 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1356 KB |
Output is correct |
| 3 |
Correct |
1 ms |
460 KB |
Output is correct |
| 4 |
Correct |
1 ms |
460 KB |
Output is correct |
| 5 |
Correct |
2 ms |
1356 KB |
Output is correct |
| 6 |
Correct |
1 ms |
460 KB |
Output is correct |
| 7 |
Correct |
3 ms |
1356 KB |
Output is correct |
| 8 |
Correct |
0 ms |
460 KB |
Output is correct |
| 9 |
Correct |
2 ms |
1356 KB |
Output is correct |
| 10 |
Correct |
103 ms |
49476 KB |
Output is correct |
| 11 |
Correct |
86 ms |
49512 KB |
Output is correct |
| 12 |
Correct |
47 ms |
24484 KB |
Output is correct |
| 13 |
Correct |
54 ms |
29332 KB |
Output is correct |
| 14 |
Correct |
93 ms |
38256 KB |
Output is correct |
| 15 |
Correct |
84 ms |
49476 KB |
Output is correct |
| 16 |
Correct |
93 ms |
50092 KB |
Output is correct |
| 17 |
Correct |
77 ms |
47432 KB |
Output is correct |
| 18 |
Correct |
96 ms |
48848 KB |
Output is correct |
| 19 |
Correct |
94 ms |
48808 KB |
Output is correct |
| 20 |
Correct |
108 ms |
47552 KB |
Output is correct |
| 21 |
Correct |
86 ms |
49452 KB |
Output is correct |
| 22 |
Correct |
93 ms |
50152 KB |
Output is correct |
