oj.uz

Submission #752793

# Submission time Handle Problem Language Result Execution time Memory
752793 2023-06-03T21:02:07 Z math_rabbit_1028 Abracadabra (CEOI22_abracadabra) C++14
0 / 100
 355 ms 34220 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) {
            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 300 ms 19828 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 28404 KB Output is correct
2 Correct 353 ms 34220 KB Output is correct
3 Correct 279 ms 25856 KB Output is correct
4 Correct 269 ms 22172 KB Output is correct
5 Correct 296 ms 23536 KB Output is correct
6 Correct 251 ms 21336 KB Output is correct
7 Correct 328 ms 26184 KB Output is correct
8 Correct 333 ms 25636 KB Output is correct
9 Correct 336 ms 22844 KB Output is correct
10 Correct 350 ms 23936 KB Output is correct
11 Correct 312 ms 20224 KB Output is correct
12 Correct 298 ms 19948 KB Output is correct
13 Correct 330 ms 23832 KB Output is correct
14 Correct 295 ms 20476 KB Output is correct
15 Correct 355 ms 24416 KB Output is correct
16 Correct 25 ms 2644 KB Output is correct
17 Runtime error 261 ms 32456 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 41 ms 4032 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 19828 KB Output isn't correct
2 Halted 0 ms 0 KB -