# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
828259 |
2023-08-17T07:24:56 Z |
vjudge1 |
Editor (BOI15_edi) |
C++14 |
|
228 ms |
72456 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<ll>
#define pi pair<ll,ll>
#define fi first
#define se second
#define gcd __gcd
#define mset(a,v) memset(a, v, sizeof(a))
#define endl '\n'
const int N = 1e6 + 5,LOG = 27;
const ll MOD = 1e9 + 7,INF = 1e9;
ll n,a[N],lvl[N],up[N][LOG];
/*
Edit state: lvl[i] = 0
Undo state: lvl[i] = -a[i]
-> lift den cai active op gan nhat ma co lvl nho hon lvl[i]
*/
ll lift(ll u,ll k){
if(lvl[u] <= k) return u;
for(ll i = LOG - 1;i >= 0;--i)
if(lvl[up[u][i]] > k) u = up[u][i];
return up[u][0];
}
void solve(){
cin>>n;
for(ll i = 1;i <= n;++i) cin>>a[i];
for(ll i = 1;i <= n;++i){
if(a[i] < 0){
lvl[i] = -a[i];
ll tmp = lift(i - 1,lvl[i] - 1);
up[i][0] = lift(tmp-1,lvl[i] - 1);
for(ll j = 1;j < LOG;++j) up[i][j] = up[up[i][j-1]][j-1];
}
cout<<a[lift(i,0)]<<endl;
}
}
signed main(){
cin.tie(0); cout.tie(0);
ios_base::sync_with_stdio(false);
ll t = 1; //cin>>t;
while(t--) solve();
cerr << endl << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
3 ms |
980 KB |
Output is correct |
3 |
Correct |
1 ms |
324 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
3 ms |
1492 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
2 ms |
1492 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
2 ms |
1492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
124 ms |
71844 KB |
Output is correct |
2 |
Correct |
129 ms |
71896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
62 ms |
19720 KB |
Output is correct |
2 |
Correct |
64 ms |
23624 KB |
Output is correct |
3 |
Correct |
189 ms |
56828 KB |
Output is correct |
4 |
Correct |
127 ms |
71732 KB |
Output is correct |
5 |
Correct |
126 ms |
72440 KB |
Output is correct |
6 |
Correct |
111 ms |
69740 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
3 ms |
980 KB |
Output is correct |
3 |
Correct |
1 ms |
324 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
3 ms |
1492 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
2 ms |
1492 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
2 ms |
1492 KB |
Output is correct |
10 |
Correct |
124 ms |
71844 KB |
Output is correct |
11 |
Correct |
129 ms |
71896 KB |
Output is correct |
12 |
Correct |
62 ms |
19720 KB |
Output is correct |
13 |
Correct |
64 ms |
23624 KB |
Output is correct |
14 |
Correct |
189 ms |
56828 KB |
Output is correct |
15 |
Correct |
127 ms |
71732 KB |
Output is correct |
16 |
Correct |
126 ms |
72440 KB |
Output is correct |
17 |
Correct |
111 ms |
69740 KB |
Output is correct |
18 |
Correct |
117 ms |
39520 KB |
Output is correct |
19 |
Correct |
108 ms |
39372 KB |
Output is correct |
20 |
Correct |
228 ms |
71080 KB |
Output is correct |
21 |
Correct |
124 ms |
71824 KB |
Output is correct |
22 |
Correct |
116 ms |
72456 KB |
Output is correct |