제출 #1111478

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1111478		Kirill22	Editor (BOI15_edi)	C++17	100 / 100	423 ms	26364 KiB

edi

#include "bits/stdc++.h"

using namespace std;

const int N = 300000;
int t[4 * N];

void upd(int v, int l, int r, int i, int x) {
    if (l + 1 == r) {
        t[v] = x;
        return;
    }
    int m = (l + r) / 2;
    if (i < m) upd(v * 2 + 1, l, m, i, x);
    else upd(v * 2 + 2, m, r, i, x);
    t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
}

int get(int v, int l, int r, int x) {
    if (l + 1 == r) {
        return l;
    }
    int m = (l + r) / 2;
    if (t[v * 2 + 2] > x) {
        return get(v * 2 + 2, m, r, x);
    } else {
        return get(v * 2 + 1, l, m, x);
    }
}

void solve() {
    int n;
    cin >> n;
    fill(t, t + 4 * n, -(int) 1e9);
    vector<int> op(n), pr(n, -1), active(n), rt(n), tmp, have(n);
    for (int i = 0; i < n; i++) {
        cin >> op[i];
    }
    for (int i = 0; i < n; i++) {
        if (op[i] > 0) {
            rt[i] = i;
            tmp.push_back(i);
        } else if (op[i - 1] > op[i]) {
            pr[i] = i - 1;
            tmp.push_back(i);
        } else {
            set<int> have(tmp.begin(), tmp.end());
            while (!have.empty()) {
                int j = *have.rbegin();
                have.erase(j);
                active[j] ^= 1;
                if (active[j]) {
                    upd(0, 0, n, j, op[j]);
                } else {
                    upd(0, 0, n, j, -(int) 1e9);
                }
                if (pr[j] != -1) {
                    if (have.find(pr[j]) != have.end()) {
                        have.erase(pr[j]);
                    } else {
                        have.insert(pr[j]);
                    }
                }
            }
            pr[i] = get(0, 0, n, op[i]);
            tmp = {i};
        }
    }
    map<int, int> cnt;
    std::fill(active.begin(), active.end(), 0);
    for (int i = 0; i < n; i++) {
        if (pr[i] != -1) {
            rt[i] = rt[pr[i]];
        }
        int j = rt[i];
        active[j] ^= 1;
        if (active[j]) {
            cnt[j] = 1;
        } else {
            cnt.erase(j);
        }
        cout << (cnt.empty() ? 0 : op[cnt.rbegin()->first]) << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
}

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