Submission #1107104

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107104		Sharky	Abracadabra (CEOI22_abracadabra)	C++17	100 / 100	497 ms	45240 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
const int Q = 1e6 + 10;
int n, in[N], a[N], xi[N], yi[N], nxt[N], q, px = 1, py = 1, po[N], ans[Q];
array<int, 3> qry[Q];

struct SegTree {
    int size = 1;
    vector<int> seg;
    void init(int _n) {
        while (size < _n) size *= 2;
        seg.assign(2 * size + 10, 0);
    }
    void update(int pos, int v, int l, int r, int id) {
        if (l == r) {
            seg[id] += v;
            return;
        }
        int mid = (l + r) / 2;
        if (pos <= mid) update(pos, v, l, mid, id * 2);
        else update(pos, v, mid + 1, r, id * 2 + 1);
        seg[id] = seg[id * 2] + seg[id * 2 + 1];
    }
    int query(int ql, int qr, int l, int r, int id) {
        if (qr < l || r < ql) return 0;
        if (ql <= l && r <= qr) return seg[id];
        int mid = (l + r) / 2;
        return query(ql, qr, l, mid, id * 2) + query(ql, qr, mid + 1, r, id * 2 + 1);
    }
    int find(int l, int r, int sum, int id) {
        if (l == r) return l;
        int mid = (l + r) / 2;
        if (seg[id * 2] >= sum) return find(l, mid, sum, id * 2);
        else return find(mid + 1, r, sum - seg[id * 2], id * 2 + 1);
    }
} ST;

int get_next(int value, int dist) {
    return a[po[value] + dist];
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> in[i];
        if (i <= n / 2) xi[i] = in[i];
        else yi[i - n / 2] = in[i];
    }
    for (int i = 1; i <= n; i++) {
        if (px > n / 2) a[i] = yi[py++];
        else if (py > n / 2) a[i] = xi[px++];
        else if (xi[px] < yi[py]) a[i] = xi[px++];
        else a[i] = yi[py++];
        po[a[i]] = i;
    }
    // for (int i = 1; i <= n; i++) cout << a[i] << ' '; cout << '\n';
    stack<int> st;
    for (int i = 1; i <= n; i++) nxt[i] = 1e9;
    for (int i = n; i >= 1; i--) {
        while (!st.empty() && a[st.top()] < a[i]) st.pop();
        if (!st.empty()) nxt[i] = st.top() - i;
        st.push(i);
    }
    // for (int i = 1; i <= n; i++) cout << nxt[i] << ' '; cout << '\n';
    vector<pair<int, int>> piv;
    for (int i = 1; i <= n; i++) {
        if (piv.empty() || piv.back().first < a[i]) piv.push_back({a[i], 1});
        else piv.back().second++;
    }
    for (int i = 1; i <= q; i++) {
        cin >> qry[i][0] >> qry[i][1];
        qry[i][2] = i;
    }
    sort(qry + 1, qry + q + 1, [] (auto x, auto y) {
        return x[0] < y[0];
    });
    ST.init(n + 1);
    for (auto& [pi, pj] : piv) ST.update(pi, pj, 1, n, 1);
    int cur = 1;
    bool firm = 0;
    // for (int i = 1; i <= n; i++) cout << ST.query(i, i, 1, n, 1) << ' ';
    // cout << '\n';
    for (int i = 1; i <= q; i++) {
        int t = qry[i][0], id = qry[i][1];
        if (!t) {
            ans[qry[i][2]] = in[id];
            continue;
        }
        if (t == 1) {
            ans[qry[i][2]] = a[id];
            continue;
        }
        while (cur < t && !firm) {
            int rt = ST.find(1, n, n / 2, 1);
            int actl = ST.query(1, rt, 1, n, 1);
            int pdist = ST.query(1, rt - 1, 1, n, 1);
            if (actl == n / 2) {
                firm = 1;
                break;
            }
            // cout << "rt: " << rt << '\n';
            int ex = actl - n / 2, elapsed = 0;
            ST.update(rt, -ex, 1, n, 1);
            while (ex > 0) {
                int hd = get_next(rt, n / 2 + elapsed - pdist);
                // cout << "hd: " << hd << '\n';
                int len = min(nxt[po[hd]] - 1, ex - 1);
                // cout << "len: " << nxt[po[hd]] - 1 << " " << ex << '\n';
                ST.update(hd, len + 1, 1, n, 1);
                ex -= len + 1, elapsed += len + 1;
            }
            cur++;
            // for (int j = 1; j <= n; j++) cout << ST.query(j, j, 1, n, 1) << ' ';
            // cout << '\n';
        }
        int cutoff = ST.find(1, n, id, 1); // >=
        int actl = ST.query(1, cutoff - 1, 1, n, 1);
        int dista = id - actl - 1;
        ans[qry[i][2]] = a[po[cutoff] + dista];
    }
    // for (int i = 1; i <= n; i++) cout << ST.query(i, i, 1, n, 1) << ' ';
    // cout << '\n';
    for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
}

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