Submission #752804

#	Time	Username	Problem	Language	Result	Execution time	Memory
752804		math_rabbit_1028	Abracadabra (CEOI22_abracadabra)	C++14	100 / 100	817 ms	49140 KiB

Main

#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());
        }
        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});
        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: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25