oj.uz

Submission #145531

# Submission time Handle Problem Language Result Execution time Memory
145531 2019-08-20T11:02:32 Z Vlatko Editor (BOI15_edi) C++14
100 / 100
 519 ms 207680 KB 
#include <bits/stdc++.h>
using namespace std;

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 300010;

struct PersTree {
    // simple persistent segment tree
    // the find query is a bit simpler than normal
    struct Node {
        Node *l, *r;
        int minval;
        Node() : l(nullptr), r(nullptr), minval(maxn) {}
        Node(int val) : l(nullptr), r(nullptr), minval(val) {}
        Node(Node *l, Node *r) : l(l), r(r), minval(maxn) {
            if (l) minval = min(minval, l->minval);
            if (r) minval = min(minval, r->minval);
        }
    };
    Node* roots[maxn];
    Node* build(int tl, int tr) {
        if (tl == tr) return new Node();
        int tm = (tl + tr) / 2;
        return new Node(build(tl, tm), build(tm+1, tr));
    }
    Node* update(Node* v, int tl, int tr, int pos, int val) {
        if (tl == tr) return new Node(val);
        int tm = (tl + tr) / 2;
        if (pos <= tm) {
            return new Node(update(v->l, tl, tm, pos, val), v->r);
        } else {
            return new Node(v->l, update(v->r, tm+1, tr, pos, val));
        }
    }
    // find max. pos with val < wanted val
    // like doing prev(lower_bound) on an array
    int find(Node* v, int tl, int tr, int val) {
        if (tl == tr) return tl;
        int tm = (tl + tr) / 2;
        if (v->r->minval < val) {
            return find(v->r, tm+1, tr, val);
        } else {
            return find(v->l, tl, tm, val);
        }
    }
} tree;

int n;
int ans[maxn];

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    ans[0] = 0;
    tree.roots[0] = tree.build(1, n);
    for (int i = 1; i <= n; ++i) {
        int a;
        cin >> a;
        if (a > 0) {
            // state now = the state right before
            // (but also add this action)
            ans[i] = a;
            tree.roots[i] = tree.update(tree.roots[i-1], 1, n, i, 0);
        } else {
            a = -a;
            // state now = the state BEFORE the action we are undoing
            // (but also add this action)
            int j = tree.find(tree.roots[i-1], 1, n, a) - 1;
            ans[i] = ans[j];
            tree.roots[i] = tree.update(tree.roots[j], 1, n, i, a);
        }
        cout << ans[i] << '\n';
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 8 ms 3068 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 8 ms 2940 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 8 ms 2936 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 9 ms 2936 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 471 ms 206952 KB Output is correct
2 Correct 480 ms 207052 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 99084 KB Output is correct
2 Correct 272 ms 120440 KB Output is correct
3 Correct 431 ms 162316 KB Output is correct
4 Correct 493 ms 207040 KB Output is correct
5 Correct 509 ms 207608 KB Output is correct
6 Correct 519 ms 204920 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 8 ms 3068 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 8 ms 2940 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 8 ms 2936 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 9 ms 2936 KB Output is correct
10 Correct 471 ms 206952 KB Output is correct
11 Correct 480 ms 207052 KB Output is correct
12 Correct 224 ms 99084 KB Output is correct
13 Correct 272 ms 120440 KB Output is correct
14 Correct 431 ms 162316 KB Output is correct
15 Correct 493 ms 207040 KB Output is correct
16 Correct 509 ms 207608 KB Output is correct
17 Correct 519 ms 204920 KB Output is correct
18 Correct 467 ms 207680 KB Output is correct
19 Correct 461 ms 207544 KB Output is correct
20 Correct 511 ms 206140 KB Output is correct
21 Correct 468 ms 206980 KB Output is correct
22 Correct 474 ms 207608 KB Output is correct