oj.uz

답안 #145534

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
145534 2019-08-20T11:04:21 Z Vlatko Editor (BOI15_edi) C++14
100 / 100
 570 ms 207140 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);
        }
    };
    vector<Node*> roots;
    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.push_back(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.push_back(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.push_back(tree.update(tree.roots[j], 1, n, i, a));
        }
        cout << ans[i] << '\n';
    }
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 8 ms 2852 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 1 ms 376 KB Output is correct
5 Correct 8 ms 2812 KB Output is correct
6 Correct 2 ms 388 KB Output is correct
7 Correct 8 ms 2808 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 8 ms 2936 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 470 ms 206940 KB Output is correct
2 Correct 476 ms 206872 KB Output is correct

Subtask #3
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 231 ms 99156 KB Output is correct
2 Correct 274 ms 120480 KB Output is correct
3 Correct 380 ms 162276 KB Output is correct
4 Correct 469 ms 207112 KB Output is correct
5 Correct 473 ms 207068 KB Output is correct
6 Correct 447 ms 204892 KB Output is correct

Subtask #4
37.0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 8 ms 2852 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 1 ms 376 KB Output is correct
5 Correct 8 ms 2812 KB Output is correct
6 Correct 2 ms 388 KB Output is correct
7 Correct 8 ms 2808 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 8 ms 2936 KB Output is correct
10 Correct 470 ms 206940 KB Output is correct
11 Correct 476 ms 206872 KB Output is correct
12 Correct 231 ms 99156 KB Output is correct
13 Correct 274 ms 120480 KB Output is correct
14 Correct 380 ms 162276 KB Output is correct
15 Correct 469 ms 207112 KB Output is correct
16 Correct 473 ms 207068 KB Output is correct
17 Correct 447 ms 204892 KB Output is correct
18 Correct 498 ms 207088 KB Output is correct
19 Correct 492 ms 207068 KB Output is correct
20 Correct 570 ms 205828 KB Output is correct
21 Correct 527 ms 207068 KB Output is correct
22 Correct 496 ms 207140 KB Output is correct