# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
726158 |
2023-04-18T15:06:36 Z |
_martynas |
Editor (BOI15_edi) |
C++11 |
|
1016 ms |
18536 KB |
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e8;
const int JUMP_REQ_LEN = 450; // required len for the jump
struct Node {
int val = 0, lvl = 0;
// a - what should the node be if this was replaced
// b - where should you look for the lower level node
Node *a = nullptr, *b = nullptr;
Node *b_jump = nullptr;
int mn_jump = INF;
Node(int _val = 0, int _lvl = 0, Node* _a = nullptr, Node* _b = nullptr)
: val(_val), lvl(_lvl), a(_a), b(_b){
}
};
int n;
Node* root;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
root = new Node(0, n+1);
for(int i = 0; i < n; i++) {
int x; cin >> x;
if(x > 0) {
Node* curr = new Node(x, 0, root, root);
root = curr;
}
else {
int lvl = -x;
Node* curr = new Node(-1, lvl, root);
Node* it = root;
int jumped = 0;
while(it->b_jump != nullptr && it->mn_jump >= lvl) {
it = it->b_jump;
jumped++;
}
int cnt = 0;
while(it->lvl >= lvl) {
it = it->b;
cnt++;
}
// if(rand() % 32 == 1) {
// cerr << i << ":\n";
// cerr << "jumped: " << jumped << "\n";
// cerr << "w\\o jumping: " << cnt << "\n";
// }
curr->val = it->a->val;
curr->b = it->a;
root = curr;
}
cout << root->val << "\n";
Node* it = root;
int mn = INF;
int cnt = 0;
for(; it != nullptr && cnt < JUMP_REQ_LEN; cnt++) {
mn = min(mn, it->lvl);
it = it->b;
}
if(cnt == JUMP_REQ_LEN) {
root->b_jump = it;
root->mn_jump = mn;
}
}
return 0;
}
/*
7
2
5
-1
-3
-2
-4
-4
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
5 ms |
596 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
320 KB |
Output is correct |
5 |
Correct |
7 ms |
596 KB |
Output is correct |
6 |
Correct |
0 ms |
320 KB |
Output is correct |
7 |
Correct |
2 ms |
596 KB |
Output is correct |
8 |
Correct |
1 ms |
324 KB |
Output is correct |
9 |
Correct |
7 ms |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
524 ms |
17728 KB |
Output is correct |
2 |
Correct |
553 ms |
17740 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
162 ms |
9164 KB |
Output is correct |
2 |
Correct |
201 ms |
10952 KB |
Output is correct |
3 |
Correct |
684 ms |
13760 KB |
Output is correct |
4 |
Correct |
466 ms |
17912 KB |
Output is correct |
5 |
Correct |
460 ms |
18392 KB |
Output is correct |
6 |
Correct |
307 ms |
15728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
5 ms |
596 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
320 KB |
Output is correct |
5 |
Correct |
7 ms |
596 KB |
Output is correct |
6 |
Correct |
0 ms |
320 KB |
Output is correct |
7 |
Correct |
2 ms |
596 KB |
Output is correct |
8 |
Correct |
1 ms |
324 KB |
Output is correct |
9 |
Correct |
7 ms |
596 KB |
Output is correct |
10 |
Correct |
524 ms |
17728 KB |
Output is correct |
11 |
Correct |
553 ms |
17740 KB |
Output is correct |
12 |
Correct |
162 ms |
9164 KB |
Output is correct |
13 |
Correct |
201 ms |
10952 KB |
Output is correct |
14 |
Correct |
684 ms |
13760 KB |
Output is correct |
15 |
Correct |
466 ms |
17912 KB |
Output is correct |
16 |
Correct |
460 ms |
18392 KB |
Output is correct |
17 |
Correct |
307 ms |
15728 KB |
Output is correct |
18 |
Correct |
432 ms |
18536 KB |
Output is correct |
19 |
Correct |
334 ms |
18252 KB |
Output is correct |
20 |
Correct |
1016 ms |
17084 KB |
Output is correct |
21 |
Correct |
417 ms |
17884 KB |
Output is correct |
22 |
Correct |
463 ms |
18488 KB |
Output is correct |