Submission #1280877

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280877		uranium235	Editor (BOI15_edi)	C++17	15 / 100	190 ms	37668 KiB

edi

#include <bits/stdc++.h>
using namespace std;
const int inf = INT32_MAX / 2;

template <class a, class b> ostream& operator<<(ostream &l, const pair<a, b> &r) {
    l << "(" << r.first << ", " << r.second << ")";
    return l;
}

template <class t> ostream& operator<<(ostream &l, const vector<t> &r) {
    l << "{";
    for (int i = 0; i + 1 < r.size(); i++) l << r[i] << ", ";
    if (!r.empty()) l << r.back();
    l << "}";
    return l;
};

struct segtree {
    vector<pair<int, int>> a;
    vector<set<int>> base;
    int n;
    segtree(int n) : n(n), a(4 * n, {inf, -1}), base(n) {}
    pair<int, int> qry(int ql, int qr, int l, int r, int v) {
        if (r < ql || qr < l) return {inf, -1};
        else if (ql <= l && r <= qr) return a[v];
        else {
            int m = (l + r) / 2;
            return min(qry(ql, qr, l, m, 2 * v), qry(ql, qr, m + 1, r, 2 * v + 1));
        }
    }
    pair<int, int> qry(int ql, int qr) {
        return qry(ql, qr, 0, n - 1, 1);
    }
    void upd(int l, int r, int v, int i, int x, bool mod) {
        if (l == r) {
            if (mod) {
                bool added = base[i].insert(x).second;
                assert(added);
            } else {
                bool removed = base[i].erase(x);
                assert(removed);
            }
            a[v] = base[i].empty() ? make_pair(inf, -1) : make_pair(*base[i].begin(), i);
        } else {
            int m = (l + r) / 2;
            if (i <= m) upd(l, m, 2 * v, i, x, mod);
            else upd(m + 1, r, 2 * v + 1, i, x, mod);

            a[v] = min(a[2 * v], a[2 * v + 1]);
        }
    }
    void upd(int i, int x, bool mod) {
        upd(0, n - 1, 1, i, x, mod);
    }
};

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

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i] *= -1;
    }

    vector<int> parity(n), p(n, -1);
    segtree tree(n + 1);
    
    for (int i = n - 1; i >= 0; i--) {
        int level = max(0, a[i]);
        pair<int, int> ans;
        while ((ans = tree.qry(level + 1, n)).second != -1) {
            // cout << i << " " << ans << endl;
            parity[i] = 1 - parity[ans.first];
            tree.upd(ans.second, ans.first, false);
            assert(p[ans.first] == -1);
            p[ans.first] = i;
            // cout << "link " << i << " " << ans.first << endl;
            if (parity[ans.first]) {

            } else {
                break;
            }
        }
        tree.upd(level, i, true);
    }

    vector<int> root(n);
    for (int i = 0; i < n; i++) {
        if (p[i] == -1) root[i] = i;
        else root[i] = root[p[i]];
    }

    set<int> states;
    for (int i = 0; i < n; i++) {
        set<int>::iterator it = states.find(root[i]);
        if (it == states.end()) {
            states.insert(root[i]);
        } else {
            states.erase(it);
        }
        if (states.empty()) cout << 0;
        else {
            cout << -a[*states.rbegin()];
        }
        cout << '\n';
    }

    // cout << p << endl;
    // cout << root << endl;
}

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