oj.uz

Submission #752776

# Submission time Handle Problem Language Result Execution time Memory
752776 2023-06-03T20:47:40 Z math_rabbit_1028 Abracadabra (CEOI22_abracadabra) C++14
0 / 100
 368 ms 34120 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++) {
        if (queries[qnum].time == t) {
            for (set<segment>::iterator iter = segs.begin(); iter != segs.end(); iter++) {
                for (int i = iter->ed; i >= iter->st; i--) {
                    assert(p >= 1);
                    res[p--] = arr[i];
                }
            }
        }
        while (1) {
            if (queries[qnum].time != t) break;
            ans[queries[qnum].ord] = res[queries[qnum].idx];
            qnum++;
        }

        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--) {
                res[p--] = arr[i];
            }
            segs.erase(segs.begin());
        }
        if (cnt >= n/2) continue;
        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 (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 279 ms 13988 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 28344 KB Output is correct
2 Correct 325 ms 34120 KB Output is correct
3 Correct 270 ms 25832 KB Output is correct
4 Correct 252 ms 22316 KB Output is correct
5 Correct 266 ms 23588 KB Output is correct
6 Correct 244 ms 21196 KB Output is correct
7 Correct 294 ms 26236 KB Output is correct
8 Correct 292 ms 25508 KB Output is correct
9 Correct 260 ms 22888 KB Output is correct
10 Correct 270 ms 23940 KB Output is correct
11 Correct 247 ms 20176 KB Output is correct
12 Correct 238 ms 20000 KB Output is correct
13 Correct 266 ms 23904 KB Output is correct
14 Correct 279 ms 20428 KB Output is correct
15 Correct 283 ms 24464 KB Output is correct
16 Correct 18 ms 2644 KB Output is correct
17 Runtime error 173 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 36 ms 2852 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

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