제출 #145113

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
145113		Vlatko	Editor (BOI15_edi)	C++14	15 / 100	222 ms	31796 KiB

edi

#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;

int n;
int level[maxn];
int eval[maxn]; // value for e
int uptr[maxn]; // e that u is pointing to
set<int> opidx[maxn]; // indexes at level

struct segtree {
    int tree[4*maxn];
    void build() {
        for (int i = 0; i < 4*maxn; ++i) {
            tree[i] = -1;
        }
    }
    void update(int v, int tl, int tr, int pos, int num) {
        if (tl == tr) {
            tree[v] = num;
        } else {
            int tm = (tl + tr) / 2;
            if (pos <= tm) {
                update(2*v, tl, tm, pos, num);
            } else {
                update(2*v+1, tm+1, tr, pos, num);
            }
            tree[v] = max(tree[2*v], tree[2*v+1]);
        }
    }
    int query(int v, int tl, int tr, int l, int r) {
        if (l > r) return -1;
        if (l <= tl && tr <= r) return tree[v];
        int tm = (tl + tr) / 2;
        return max(query(2*v, tl, tm, l, min(r, tm)),
                   query(2*v+1, tm+1, tr, max(l, tm+1), r));
    }
} tree; // max idx of active operation in this range of levels

void add(int i) {
    opidx[level[i]].insert(i);
    if (*opidx[level[i]].rbegin() == i) {
        tree.update(1, 0, n, level[i], i);
    }
}

void remove(int i) {
    bool should_update = *opidx[level[i]].rbegin() == i;
    opidx[level[i]].erase(i);
    if (should_update) {
        if (opidx[level[i]].empty()) {
            tree.update(1, 0, n, level[i], -1);
        } else {
            tree.update(1, 0, n, level[i], *opidx[level[i]].rbegin());
        }
    }
}

void process_edit(int i, int x) {
    // cout << "edit: "; debug(i, x);
    level[i] = 0;
    eval[i] = x;
    add(i);
}

void process_undo(int i, int lvl) {
    int j = tree.query(1, 0, n, 0, lvl-1);
    // cout << "undo: "; debug(i, lvl, j, level[j]);
    while (j == -1) {}
    if (level[j] == 0) {
        // edit operation
        level[i] = lvl;
        uptr[i] = j;
        remove(j);
        add(i);
    } else {
        // undo operation, pointing to edit operation
        remove(j);
        add(uptr[j]);
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    tree.build();
    process_edit(0, 0);
    for (int i = 1; i <= n; ++i) {
        int a;
        cin >> a;
        if (a > 0) {
            process_edit(i, a);
        } else {
            process_undo(i, -a);
        }
        cout << eval[tree.query(1, 0, n, 0, 0)] << '\n';
    }
}

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