Submission #752610

#	Time	Username	Problem	Language	Result	Execution time	Memory
752610		math_rabbit_1028	Abracadabra (CEOI22_abracadabra)	C++14	0 / 100	285 ms	21636 KiB

Main

#include <bits/stdc++.h>
using namespace std;
int n, q, arr[1010];

int ans[1010101];
int res[202020];

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++;
    }

    int v = arr[1], s = 1;
    for (int i = 2; i <= n/2; i++) {
        if (v < arr[i]) {
            segs.insert({v, s, i - 1, i - s});
            v = arr[i];
            s = i;
        }
    }
    segs.insert({v, s, n/2, n/2 - s + 1});

    v = arr[n/2 + 1], s = n/2 + 1;
    for (int i = n/2 + 2; i <= n; i++) {
        if (v < arr[i]) {
            segs.insert({v, s, i - 1, i - s});
            v = arr[i];
            s = i;
        }
    }
    segs.insert({v, s, n, n - s + 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 (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());
        }
        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});
        s = div.st + cnt + div.sz - n/2; v = arr[s];
        for (int i = s; i <= div.ed; i++) {
            if (v < arr[i]) {
                segs.insert({v, s, i - 1, i - s});
                v = arr[i];
                s = i;
            }
        }
        segs.insert({v, s, div.ed, div.ed - s + 1});
    }

    for (int i = 1; i <= q; i++) cout << ans[i] << "\n";

    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 40
• Subtask 3: 0 / 25
• Subtask 4: 0 / 25