Submission #402556

#	Time	Username	Problem	Language	Result	Execution time	Memory
402556		gevacrt	Editor (BOI15_edi)	C++17	100 / 100	492 ms	270420 KiB

edi

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

#define INF INT_MAX
#define MOD 1000000007
#define all(x) x.begin(), x.end()

struct PersTree {
    PersTree *l, *r;
    int key, val, max_val;

    PersTree(PersTree *_l, PersTree *_r, int _key, int _val, int _max_val) : 
        l(_l), r(_r), key(_key), val(_val), max_val(_max_val) {}

    PersTree *insert(int _key, int _val){
        PersTree *_l = l, *_r = r;
        int nval = val;

        if(_key < key) _l = _l->insert(_key, _val);
        else if(_key == key) nval = _val;
        else _r = _r->insert(_key, _val);

        return new PersTree(_l, _r, key, nval, max({(_l?_l->max_val:0), nval, (_r?_r->max_val:0)}));
    }

    int query(int _key){
        if(_key < key) return l->query(_key);
        else if(_key == key) return max((l?l->max_val:0), val);
        else return max({(l?l->max_val:0), val, r->query(_key)});
    }
};

PersTree *build(int left, int right){
    if(left > right) return NULL;
    int m = (left+right)/2;
    return new PersTree(build(left, m-1), build(m+1, right), m, 0, 0);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N; cin >> N;

    vector<PersTree*> A(N+1);
    A[0] = build(0, N);
    vi ans(N+1);

    for(int i = 1; i <= N; i++){
        int x; cin >> x;
        if(x > 0){
            // write operation
            ans[i] = x;
            A[i] = A[i-1]->insert(0, i);

        }else{
            // undo operation
            int prv = A[i-1]->query(-x-1)-1;
            ans[i] = ans[prv];
            A[i] = A[prv]->insert(-x, i);
        }
        cout << ans[i] << "\n";
        A[1]->query(10);
    }

    return 0;
}

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