Submission #726158

#	Time	Username	Problem	Language	Result	Execution time	Memory
726158		_martynas	Editor (BOI15_edi)	C++11	100 / 100	1016 ms	18536 KiB

edi

#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


*/

• Subtask 1: 20 / 20
• Subtask 2: 15 / 15
• Subtask 3: 28 / 28
• Subtask 4: 37 / 37