oj.uz

Submission #752796

# Submission time Handle Problem Language Result Execution time Memory
752796 2023-06-03T21:05:41 Z math_rabbit_1028 Abracadabra (CEOI22_abracadabra) C++14
0 / 100
 3000 ms 35168 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++) {
        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--) {
                    res[p--] = arr[i];
                }
            }
        }
 
        while (qnum <= q) {
            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());
        }
        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 14156 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 28248 KB Output is correct
2 Correct 347 ms 34112 KB Output is correct
3 Correct 294 ms 25960 KB Output is correct
4 Correct 276 ms 22160 KB Output is correct
5 Correct 270 ms 23656 KB Output is correct
6 Correct 297 ms 21092 KB Output is correct
7 Correct 344 ms 26120 KB Output is correct
8 Correct 289 ms 25576 KB Output is correct
9 Correct 258 ms 22800 KB Output is correct
10 Correct 278 ms 24128 KB Output is correct
11 Correct 258 ms 20152 KB Output is correct
12 Correct 249 ms 19916 KB Output is correct
13 Correct 270 ms 23884 KB Output is correct
14 Correct 254 ms 20596 KB Output is correct
15 Correct 295 ms 24460 KB Output is correct
16 Correct 18 ms 2644 KB Output is correct
17 Correct 284 ms 35168 KB Output is correct
18 Correct 216 ms 21364 KB Output is correct
19 Correct 59 ms 6220 KB Output is correct
20 Execution timed out 3054 ms 9164 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 2840 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 14156 KB Output isn't correct
2 Halted 0 ms 0 KB -