Submission #909983

#	Time	Username	Problem	Language	Result	Execution time	Memory
909983		Alcabel	Abracadabra (CEOI22_abracadabra)	C++17	100 / 100	881 ms	41624 KiB

Main

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

mt19937 rnd(161);

struct Node {
    int val, priority, sz, maxVal;
    int left, right;
    Node() {
        left = right = -1;
    }
    Node(int _val) {
        val = _val, sz = 1, maxVal = val;
        priority = rnd();
        left = right = -1;
    }
};

const int maxn = 2e5;
Node treap[maxn];

int getSz(int root) {
    if (root == -1) { return 0; }
    return treap[root].sz;
}

int getMax(int root) {
    if (root == -1) { return 0; }
    return treap[root].maxVal;
}

void update(int root) {
    if (root == -1) { return; }
    treap[root].sz = getSz(treap[root].left) + getSz(treap[root].right) + 1;
    treap[root].maxVal = max(max(getMax(treap[root].left), getMax(treap[root].right)), treap[root].val);
}

int merge(int l, int r) {
    if (l == -1) { return r; }
    if (r == -1) { return l; }
    if (treap[l].priority > treap[r].priority) {
        treap[l].right = merge(treap[l].right, r);
        update(l);
        return l;
    }
    treap[r].left = merge(l, treap[r].left);
    update(r);
    return r;
}

pair<int, int> split(int root, int k) {
    if (root == -1) { return {-1, -1}; }
    int lsz = getSz(treap[root].left);
    if (lsz >= k) {
        auto [l, r] = split(treap[root].left, k);
        treap[root].left = r;
        update(root);
        return {l, root};
    }
    auto [l, r] = split(treap[root].right, k - lsz - 1);
    treap[root].right = l;
    update(root);
    return {root, r};
}

int getKth(int root, int k) {
    if (root == -1) { return 0; }
    while (root != -1) {
        int lsz = getSz(treap[root].left);
        if (lsz >= k) {
            root = treap[root].left;
        } else {
            k -= lsz;
            if (k == 1) {
                break;
            }
            --k;
            root = treap[root].right;
        }
    }
    assert(root != -1);
    return treap[root].val;
}

int getFirstGreater(int root, int x) {
    if (root == -1) { return 0; }
    int res = 0;
    while (root != -1) {
        if (getMax(treap[root].left) > x) {
            root = treap[root].left;
        } else {
            res += getSz(treap[root].left);
            if (treap[root].val > x) {
                break;
            }
            root = treap[root].right;
            ++res;
        }
    }
    return res;
}

void dfs(int root) {
    if (root == -1) { return; }
    dfs(treap[root].left);
    cerr << treap[root].val << ' ';
    dfs(treap[root].right);
}

struct Query {
    int t, pos, i;
    Query() {}
    Query(int _t, int _pos, int _i) {
        t = _t, pos = _pos, i = _i;
    }
    bool operator<(const Query& other) const {
        return t < other.t;
    }
    ~Query() {}
};

void solve() {
    int n, q;
    cin >> n >> q;
    int half = n / 2, root = -1;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        treap[i] = Node(x);
        root = merge(root, i);
    }
    /*cerr << "built:\n";
    dfs(root);
    cerr << '\n';*/
    vector<Query> queries(q);
    for (int i = 0; i < q; ++i) {
        cin >> queries[i].t >> queries[i].pos;
        queries[i].i = i;
    }
    sort(queries.begin(), queries.end());
    int t = 0;
    bool cycled = false;
    vector<int> ans(q);
    for (const Query& query : queries) {
        while (!cycled && t < query.t) {
            auto [lh, rh] = split(root, half);
            int firstL = getKth(lh, 1), firstR = getKth(rh, 1);
            if (firstR > getMax(lh)) {
                cycled = true;
                root = merge(lh, rh);
            } else {
                int turn = (firstL > firstR ? 1 : -1);
                root = -1;
                while (firstL != 0 && firstR != 0) {
                    if (turn == -1) {
                        // cut from left
                        int k = getFirstGreater(lh, firstR);
                        assert(k >= 1);
                        auto [start, fin] = split(lh, k);
                        root = merge(root, start);
                        firstL = getKth(fin, 1);
                        lh = fin;
                    } else {
                        // cut from right
                        int k = getFirstGreater(rh, firstL);
                        assert(k >= 1);
                        auto [start, fin] = split(rh, k);
                        root = merge(root, start);
                        firstR = getKth(fin, 1);
                        rh = fin;
                    }
                    turn = -turn;
                }
                if (firstL == 0) {
                    root = merge(root, rh);
                } else {
                    root = merge(root, lh);
                }
            }
            ++t;
            /*cerr << "t: " << t << '\n';
            dfs(root);
            cerr << '\n';*/
        }
        ans[query.i] = getKth(root, query.pos);
    }
    for (int i = 0; i < q; ++i) {
        cout << ans[i] << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
        cerr << "-----------\n";
        cout << "-----------\n";
    }
#else
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
#endif

    return 0;
}

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