oj.uz

Submission #802695

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

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

int n, lvl[N], par[N], val[N];
priority_queue<pair<int, int>> 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<pair<int, int>> cur, nxt;
    for(int i = n-1; i > -1; i--) {
        par[i] = i;
        swap(nxt, cur);
        while(!nxt.empty()) nxt.pop();
        nxt.push({max(lvl[i], 0ll), i});
        while(!cur.empty() && cur.top().first > max(lvl[i], 0ll)) {
            int id = cur.top().second;
            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++)
        if(lvl[i] < 0)
            cout << (val[i] = -lvl[i]) << '\n';
        else
            cout << (val[i] = val[par[i]-1]) << '\n';
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9940 KB Output is correct
3 Correct 5 ms 9740 KB Output is correct
4 Correct 5 ms 9612 KB Output is correct
5 Correct 6 ms 9940 KB Output is correct
6 Correct 6 ms 9736 KB Output is correct
7 Correct 7 ms 10068 KB Output is correct
8 Correct 5 ms 9680 KB Output is correct
9 Correct 6 ms 10080 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 31040 KB Output is correct
2 Correct 71 ms 31048 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 19536 KB Output is correct
2 Correct 51 ms 21024 KB Output is correct
3 Correct 65 ms 24516 KB Output is correct
4 Correct 70 ms 31092 KB Output is correct
5 Correct 70 ms 30280 KB Output is correct
6 Correct 75 ms 29016 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 6 ms 9940 KB Output is correct
3 Correct 5 ms 9740 KB Output is correct
4 Correct 5 ms 9612 KB Output is correct
5 Correct 6 ms 9940 KB Output is correct
6 Correct 6 ms 9736 KB Output is correct
7 Correct 7 ms 10068 KB Output is correct
8 Correct 5 ms 9680 KB Output is correct
9 Correct 6 ms 10080 KB Output is correct
10 Correct 75 ms 31040 KB Output is correct
11 Correct 71 ms 31048 KB Output is correct
12 Correct 37 ms 19536 KB Output is correct
13 Correct 51 ms 21024 KB Output is correct
14 Correct 65 ms 24516 KB Output is correct
15 Correct 70 ms 31092 KB Output is correct
16 Correct 70 ms 30280 KB Output is correct
17 Correct 75 ms 29016 KB Output is correct
18 Correct 71 ms 29632 KB Output is correct
19 Correct 65 ms 28824 KB Output is correct
20 Correct 70 ms 28204 KB Output is correct
21 Correct 69 ms 31168 KB Output is correct
22 Correct 80 ms 30336 KB Output is correct