oj.uz

Submission #752795

# Submission time Handle Problem Language Result Execution time Memory
752795 2023-06-03T21:04:33 Z math_rabbit_1028 Abracadabra (CEOI22_abracadabra) C++14
0 / 100
 325 ms 35836 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 (qnum <= q) {
        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) {
            assert(segs.size() > 0);
            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];
        }
    }
    assert(p == 0);
    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 325 ms 19940 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 28232 KB Output is correct
2 Correct 323 ms 34204 KB Output is correct
3 Correct 296 ms 25832 KB Output is correct
4 Correct 253 ms 22136 KB Output is correct
5 Correct 279 ms 23616 KB Output is correct
6 Correct 251 ms 21196 KB Output is correct
7 Correct 293 ms 26188 KB Output is correct
8 Correct 281 ms 25548 KB Output is correct
9 Correct 271 ms 22812 KB Output is correct
10 Correct 274 ms 23960 KB Output is correct
11 Correct 264 ms 20152 KB Output is correct
12 Correct 251 ms 19892 KB Output is correct
13 Correct 273 ms 23976 KB Output is correct
14 Correct 252 ms 20488 KB Output is correct
15 Correct 281 ms 24560 KB Output is correct
16 Correct 18 ms 2644 KB Output is correct
17 Correct 304 ms 35836 KB Output is correct
18 Correct 221 ms 28808 KB Output is correct
19 Incorrect 68 ms 9764 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

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

Subtask #4
0 / 25.0

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