oj.uz

Submission #752803

# Submission time Handle Problem Language Result Execution time Memory
752803 2023-06-03T22:12:58 Z math_rabbit_1028 Abracadabra (CEOI22_abracadabra) C++14
0 / 100
 3000 ms 37168 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 = 1;
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;

struct segtree {
    int tree[808080];
    void update(int v, int st, int ed, int idx, int val) {
        if (st > idx) return;
        if (ed < idx) return;
        if (st == ed) {
            tree[v] = val;
            return;
        }
        int mid = (st + ed) / 2;
        update(2 * v, st, mid, idx, val);
        update(2 * v + 1, mid + 1, ed, idx, val);
        tree[v] = tree[2 * v] + tree[2 * v + 1];
    } 
    pair<int, int> get(int v, int st, int ed, int val) {
        if (st == ed) return {st, val - tree[v]};
        int mid = (st + ed) / 2;
        if (tree[2 * v] < val) return get(2 * v + 1, mid + 1, ed, val - tree[2 * v]);
        else return get(2 * v, st, mid, val);
    }
} sumtree;
 
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;
        queries[i].time = min(queries[i].time, n);
    }
    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});
        sumtree.update(1, 1, n, arr[k], nxt[k] - k);
        k = nxt[k];
    }
    segs.insert({arr[k], k, n/2, n/2 - k + 1});
    sumtree.update(1, 1, n, arr[k], n/2 - k + 1);
 
    k = n/2 + 1;
    while (nxt[k] <= n) {
        segs.insert({arr[k], k, nxt[k] - 1, nxt[k] - k});
        sumtree.update(1, 1, n, arr[k], nxt[k] - k);
        k = nxt[k];
    }
    segs.insert({arr[k], k, n, n - k + 1});
    sumtree.update(1, 1, n, arr[k], n - k + 1);
 
    int cnt = 0, p = n;
    for (int t = 1; t <= queries[q].time; t++) {
        while (qnum <= q) {
            if (queries[qnum].time > t) break;
            if (res[queries[qnum].idx] > 0) ans[queries[qnum].ord] = res[queries[qnum].idx];
            else {
                pair<int, int> val = sumtree.get(1, 1, n, queries[qnum].idx);
                assert(segs.find({val.first, 0, 0, 0}) != segs.end());
                ans[queries[qnum].ord] = arr[segs.find({val.first, 0, 0, 0})->ed + val.second];
            }
            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];
            }
            sumtree.update(1, 1, n, segs.begin()->first, 0);
            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});
        sumtree.update(1, 1, n, div.first, 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});
            sumtree.update(1, 1, n, arr[k], nxt[k] - k);
            k = nxt[k];
        }
        segs.insert({arr[k], k, div.ed, div.ed - k + 1});
        sumtree.update(1, 1, n, arr[k], 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 Runtime error 290 ms 32308 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 441 ms 29448 KB Output is correct
2 Correct 410 ms 35772 KB Output is correct
3 Correct 389 ms 26876 KB Output is correct
4 Correct 305 ms 23916 KB Output is correct
5 Correct 327 ms 25232 KB Output is correct
6 Correct 286 ms 22764 KB Output is correct
7 Correct 350 ms 27856 KB Output is correct
8 Correct 328 ms 27172 KB Output is correct
9 Correct 301 ms 24572 KB Output is correct
10 Correct 311 ms 25676 KB Output is correct
11 Correct 248 ms 21696 KB Output is correct
12 Correct 263 ms 21612 KB Output is correct
13 Correct 308 ms 25528 KB Output is correct
14 Correct 279 ms 22216 KB Output is correct
15 Correct 305 ms 26044 KB Output is correct
16 Correct 18 ms 3512 KB Output is correct
17 Correct 295 ms 37168 KB Output is correct
18 Execution timed out 3043 ms 15944 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 7580 KB Output is correct
2 Correct 126 ms 9140 KB Output is correct
3 Execution timed out 3081 ms 6796 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 290 ms 32308 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -