oj.uz

Submission #402556

# Submission time Handle Problem Language Result Execution time Memory
402556 2021-05-12T00:08:33 Z gevacrt Editor (BOI15_edi) C++17
100 / 100
 492 ms 270420 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 6 ms 3404 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 6 ms 3276 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 5 ms 3276 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 6 ms 3404 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 341 ms 267864 KB Output is correct
2 Correct 341 ms 267852 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 128032 KB Output is correct
2 Correct 223 ms 154908 KB Output is correct
3 Correct 302 ms 207000 KB Output is correct
4 Correct 346 ms 267836 KB Output is correct
5 Correct 492 ms 270268 KB Output is correct
6 Correct 329 ms 265772 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 6 ms 3404 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 6 ms 3276 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 5 ms 3276 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 6 ms 3404 KB Output is correct
10 Correct 341 ms 267864 KB Output is correct
11 Correct 341 ms 267852 KB Output is correct
12 Correct 211 ms 128032 KB Output is correct
13 Correct 223 ms 154908 KB Output is correct
14 Correct 302 ms 207000 KB Output is correct
15 Correct 346 ms 267836 KB Output is correct
16 Correct 492 ms 270268 KB Output is correct
17 Correct 329 ms 265772 KB Output is correct
18 Correct 460 ms 270420 KB Output is correct
19 Correct 385 ms 270172 KB Output is correct
20 Correct 380 ms 263592 KB Output is correct
21 Correct 348 ms 268104 KB Output is correct
22 Correct 486 ms 270412 KB Output is correct