oj.uz

Submission #802668

# Submission time Handle Problem Language Result Execution time Memory
802668 2023-08-02T13:15:26 Z someone Editor (BOI15_edi) C++14
100 / 100
 115 ms 38896 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 3e5 + 42, INF = 1e18 + 42;

struct Op {
    int id, lvl;

    bool operator <(const Op& other) const {
        return lvl < other.lvl;
    }
};

bool act[N];
int n, lvl[N], par[N];
priority_queue<Op> hid[N];

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

    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> lvl[i];
        lvl[i] = -lvl[i];
    }

    priority_queue<Op> cur, nxt;
    for(int i = n-1; i > -1; i--) {
        par[i] = i;
        swap(nxt, cur);
        while(!nxt.empty()) nxt.pop();
        nxt.push({i, max(lvl[i], 0ll)});
        while(!cur.empty() && cur.top().lvl > max(lvl[i], 0ll)) {
            int id = cur.top().id;
            cur.pop();
            par[id] = i;
            if((int)hid[id].size() > (int)nxt.size())
                swap(hid[id], nxt);
            while(!hid[id].empty()) {
                nxt.push(hid[id].top());
                hid[id].pop();
            }
        }
        swap(cur, hid[i]);
    }
    for(int i = 0; i < n; i++)
        par[i] = par[par[i]];

    set<pair<int, int>> state;
    state.insert({-1, 0});
    for(int i = 0; i < n; i++) {
        act[par[i]] = !act[par[i]];
        if(act[par[i]]) {
            state.insert({par[i], -lvl[par[i]]});
        } else {
            state.erase({par[i], -lvl[par[i]]});
        }
        auto it = state.end();
        it--;
        cout << (*it).second << '\n';
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 7 ms 10196 KB Output is correct
3 Correct 5 ms 9728 KB Output is correct
4 Correct 5 ms 9732 KB Output is correct
5 Correct 6 ms 9940 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 6 ms 9992 KB Output is correct
8 Correct 5 ms 9732 KB Output is correct
9 Correct 7 ms 10068 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 30460 KB Output is correct
2 Correct 82 ms 30496 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 24060 KB Output is correct
2 Correct 91 ms 26460 KB Output is correct
3 Correct 74 ms 24256 KB Output is correct
4 Correct 95 ms 30444 KB Output is correct
5 Correct 115 ms 35008 KB Output is correct
6 Correct 62 ms 27780 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 7 ms 10196 KB Output is correct
3 Correct 5 ms 9728 KB Output is correct
4 Correct 5 ms 9732 KB Output is correct
5 Correct 6 ms 9940 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 6 ms 9992 KB Output is correct
8 Correct 5 ms 9732 KB Output is correct
9 Correct 7 ms 10068 KB Output is correct
10 Correct 96 ms 30460 KB Output is correct
11 Correct 82 ms 30496 KB Output is correct
12 Correct 65 ms 24060 KB Output is correct
13 Correct 91 ms 26460 KB Output is correct
14 Correct 74 ms 24256 KB Output is correct
15 Correct 95 ms 30444 KB Output is correct
16 Correct 115 ms 35008 KB Output is correct
17 Correct 62 ms 27780 KB Output is correct
18 Correct 112 ms 38896 KB Output is correct
19 Correct 111 ms 38060 KB Output is correct
20 Correct 73 ms 27960 KB Output is correct
21 Correct 87 ms 30520 KB Output is correct
22 Correct 109 ms 35060 KB Output is correct