Submission #1236136

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236136		countless	Abracadabra (CEOI22_abracadabra)	C++20	35 / 100	3096 ms	40544 KiB

Main

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

typedef long long ll;
typedef long double ld;

#define sp <<" "<<
#define endl "\n"

struct segtree {
    int l, r;
    int val;
    segtree *left, *right;

    void merge() {
        val = left->val + right->val;
    }

    segtree(int l, int r) : l(l), r(r) {
        if (l == r) {
            left = right = nullptr;
            val = 0;
            return;
        }

        int m = (l+r) / 2;
        left = new segtree(l, m);
        right = new segtree(m+1, r);
        merge();
    }

    void update(int ind, int upd) {
        if (l == r) {
            val += upd;
            return;
        }

        int m = (l+r) / 2;
        if (ind <= m) left->update(ind, upd);
        else right->update(ind, upd);
        merge();
    }

    int query(int ind) {
        if (ind < l) return 0;
        if (ind >= r) return val;

        return left->query(ind) + right->query(ind);
    }

    int find(int x) {
        if (l == r) return l;

        if (left->val >= x) return left->find(x);
        else return right->find(x - left->val);
    }
};

void solve() {
    int n, q; cin >> n >> q;
    int half = n/2;
    using block = tuple<int, int>;
    vector<int> a(n+1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    vector<block> queries(q);
    for (int i = 0; i < q; i++) {
        int t, x; cin >> t >> x;
        t = min(t, n);
        queries[i] = {t, x};
    }

    vector<int> ans(q, -1);
    vector<int> o(q);
    iota(o.begin(), o.end(), 0);
    sort(o.begin(), o.end(), [&](int i, int j) {
        return queries[i] < queries[j];
    });

    vector<block> st(n+1), real;
    set<block> avail;
    vector<int> p(n+1);
    iota(p.begin(), p.end(), 0);
    sort(p.begin(), p.end(), [&](int i, int j) {
        return a[i] < a[j];
    });

    for (int i = 1; i <= n; i++) {
        int at = p[i];
        auto left = avail.lower_bound(make_tuple(at, at));
        auto right = avail.lower_bound(make_tuple(at, at));

        bool ok1 = false, ok2 = false;
        if (left != avail.begin()) {
            left--;
            if (get<1>(*left) == at - 1) {
                ok1 = true;
            }
        }

        if (right != avail.end()){
            if (get<0>(*right) == at + 1) {
                st[i] = make_tuple(at, get<1>(*right));
                ok2 = true;
            }
        }

        if (!ok2) {
            st[i] = make_tuple(at, at);
        }

        if (ok1 and ok2) {
            block nwe = make_tuple(get<0>(*left), get<1>(*right));
            avail.erase(left);
            avail.erase(right);
            avail.insert(nwe);
        } else if (ok1) {
            block nwe = make_tuple(get<0>(*left), at);
            avail.erase(left);
            avail.insert(nwe);
        } else if (ok2) {
            block nwe = make_tuple(at, get<1>(*right));
            avail.erase(right);
            avail.insert(nwe);
        } else {
            avail.insert(make_tuple(at, at));
        }
    }

    using state = tuple<int, int, int>;
    set<state> ts;
    int done = n;
    segtree tr(1, n);
    vector<int> temp(n+1, -1);

    {
        int i = 1;
        while (i <= n) {
            int x = a[i];
            auto [l, r] = st[x];
            int sz = r - l + 1;
            tr.update(x, sz);
            ts.emplace(x, l, r);
            i = r+1;
        }
    }

    auto fix = [&]() -> void {
        while (!ts.empty()) {
            int need = done - half;
            auto it = prev(ts.end());
            auto [x, l, r] = *it;
            int sz = r - l + 1;
            if (sz <= need) {
                tr.update(x, -sz);
                ts.erase(it);
                for (int i = r; i >= l; i--) {
                    temp[done--] = a[i];
                }
            } else {
                break;
            }
        }
    };

    fix();

    int t = 0, i = 0;
    while (done > half) {
        while (i < q and get<0>(queries[o[i]]) == t) {
            auto [tt, x] = queries[o[i]];
            int rep;
            if (x > done) {
                rep = temp[x];
            } else {
                int ele = tr.find(x);
                int amt = tr.query(ele);
                int pre = tr.query(ele - 1);
                int trav = x - pre - 1;
                auto [l, r] = st[ele];
                int j = l;
                while (j <= r and trav) {
                    j++;
                    trav--;
                }

                rep = a[j];
            }

            ans[o[i]] = rep;
            i++;
        }

        auto it = prev(ts.end());
        auto [x, l, r] = *it;
        if (x == 3) cerr << "Here" << endl;
        tr.update(x, -(r - l + 1));
        ts.erase(it);
        int loc = done - (r - l);
        
        int j = l+1;
        while (j <= r) {
            int y = a[j];
            auto [lo, hi] = st[y];
            if (half < lo - l + loc) {
                int sz = min(hi - lo + 1, done - (lo - l + loc) + 1);
                if (y == 3) cerr << y sp sz << endl;
                tr.update(y, sz);
                ts.emplace(y, lo, lo + sz - 1);
                j = hi+1;
            } else {
                j++;
            }
        }

        st[x] = make_tuple(l, l + half - loc);
        tr.update(x, half - loc + 1);
        ts.emplace(x, l, l + half - loc);

        fix();

        t++;
    }

    while (i < q) {
        auto [tt, x] = queries[o[i]];
        int rep;
        if (x > done) {
            rep = temp[x];
        } else {
            int ele = tr.find(x);
            int amt = tr.query(ele);
            int pre = tr.query(ele - 1);
            int trav = x - pre - 1;
            auto [l, r] = st[ele];
            int j = l;
            while (j <= r and trav) {
                j++;
                trav--;
            }

            rep = a[j];
        }

        ans[o[i]] = rep;
        i++;
    }

    for (auto &x : ans) {
        cout << x << endl;
    }
}

signed main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    int t = 1;
    // cin >> t;
    while (t--)
        solve();
}
// let it be known that i was tortured by my own bugs.

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