oj.uz

Submission #752791

# Submission time Handle Problem Language Result Execution time Memory
752791 2023-06-03T20:59:15 Z math_rabbit_1028 Abracadabra (CEOI22_abracadabra) C++14
0 / 100
 330 ms 34212 KB 
#include <bits/stdc++.h>
using namespace std;
int n, q, arr[202020];
 
int ans[1010101];
int res[202020];
int nxt[202020];
stack< pair<int, int> > S;
 
int qnum = 0;
struct query {
    int time, idx, ord;
    bool operator<(const query &other) const {
        if (time == other.time) return idx < other.idx;
        return time > other.time;
    }
} queries[1010101];
 
struct segment {
    int first, st, ed, sz;
    bool operator<(const segment &other) const {
        return first > other.first;
    }
};
set<segment> segs;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> arr[i];
 
    for (int i = 1; i <= q; i++) {
        cin >> queries[i].time >> queries[i].idx;
        queries[i].ord = i;
    }
    sort(queries + 1, queries + q + 1);
 
    while (1) {
        if (queries[qnum].time > 0) break;
        ans[queries[qnum].ord] = arr[queries[qnum].idx];
        qnum++;
    }

    for (int i = 1; i <= n; i++) {
        while (!S.empty()) {
            if (S.top().second < arr[i]) {
                nxt[S.top().first] = i;
                S.pop();
            }
            else break;
        }
        S.push({i, arr[i]});
    }
    while (!S.empty()) {
        nxt[S.top().first] = n + 1;
        S.pop();
    }
 
    int k = 1;
    while (nxt[k] <= n/2) {
        segs.insert({arr[k], k, nxt[k] - 1, nxt[k] - k});
        k = nxt[k];
    }
    segs.insert({arr[k], k, n/2, n/2 - k + 1});
 
    k = n/2 + 1;
    while (nxt[k] <= n) {
        segs.insert({arr[k], k, nxt[k] - 1, nxt[k] - k});
        k = nxt[k];
    }
    segs.insert({arr[k], k, n, n - k + 1});
 
    int cnt = 0, p = n;
    for (int t = 1; t < queries[q].time; t++) {
        while (1) {
            if (cnt + segs.begin()->sz > n/2) break;
            cnt += segs.begin()->sz;
            for (int i = segs.begin()->ed; i >= segs.begin()->st; i--) {
                assert(p >= 1);
                res[p--] = arr[i];
            }
            segs.erase(segs.begin());
        }
        if (cnt == n/2) break;
        segment div = *segs.begin();
        segs.erase(segs.begin());
        segs.insert({div.first, div.st, div.st + cnt + div.sz - n/2 - 1, cnt + div.sz - n/2});
        k = div.st + cnt + div.sz - n/2;
        while (nxt[k] <= div.ed) {
            segs.insert({arr[k], k, nxt[k] - 1, nxt[k] - k});
            k = nxt[k];
        }
        segs.insert({arr[k], k, div.ed, div.ed - k + 1});
    }
 

    for (set<segment>::iterator iter = segs.begin(); iter != segs.end(); iter++) {
        for (int i = iter->ed; i >= iter->st; i--) {
            res[p--] = arr[i];
        }
    }
    for (int i = 1; i <= q; i++) {
        ans[queries[i].ord] = res[queries[i].idx];
    }

    for (int i = 1; i <= q; i++) cout << ans[i] << "\n";
 
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 300 ms 19916 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 28200 KB Output is correct
2 Correct 330 ms 34212 KB Output is correct
3 Correct 273 ms 25828 KB Output is correct
4 Correct 258 ms 22244 KB Output is correct
5 Correct 290 ms 23628 KB Output is correct
6 Correct 262 ms 21116 KB Output is correct
7 Correct 289 ms 26280 KB Output is correct
8 Correct 306 ms 25468 KB Output is correct
9 Correct 273 ms 22832 KB Output is correct
10 Correct 285 ms 24020 KB Output is correct
11 Correct 235 ms 20232 KB Output is correct
12 Correct 250 ms 20008 KB Output is correct
13 Correct 286 ms 24020 KB Output is correct
14 Correct 251 ms 20540 KB Output is correct
15 Correct 283 ms 24468 KB Output is correct
16 Correct 18 ms 2644 KB Output is correct
17 Runtime error 188 ms 32492 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 3968 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 300 ms 19916 KB Output isn't correct
2 Halted 0 ms 0 KB -