Submission #1232770

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232770		ProtonDecay314	Abracadabra (CEOI22_abracadabra)	C++20	100 / 100	836 ms	32680 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> v3i;
typedef vector<v3i> v4i;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
#define INF(dt) numeric_limits<dt>::max()
#define NINF(dt) numeric_limits<dt>::min()
#define pb push_back

struct Random {
    mt19937 rnd;

    Random(): rnd(random_device{}()) {
        rnd.seed(chrono::system_clock::now().time_since_epoch().count());
    }

    int rand_int(int l, int r) {
        return uniform_int_distribution(l, r)(rnd);
    }
};

Random rnd;

/*
Range max treap
*/
struct Treap {
    Treap* lt, *rt;
    int sz, mx, v, pr;

    Treap(int a_v): lt(nullptr), rt(nullptr), sz(1), mx(a_v), v(a_v), pr(rnd.rand_int(0, numeric_limits<int>::max())) {};
};

inline int treap_sz(Treap* tr) {
    return (tr == nullptr ? 0 : tr->sz);
}

inline Treap* treap_pull(Treap* tr) {
    if(tr == nullptr) return tr;
    tr->sz = treap_sz(tr->lt) + treap_sz(tr->rt) + 1;

    tr->mx = tr->v;

    if(tr->lt != nullptr) tr->mx = max(tr->mx, tr->lt->mx);
    if(tr->rt != nullptr) tr->mx = max(tr->mx, tr->rt->mx);
    return tr;
} 

inline Treap* treap_merge(Treap* t1, Treap* t2) {
    if(t1 == nullptr) return t2;
    if(t2 == nullptr) return t1;

    if(t1->pr < t2->pr) {
        // make t2 the right child of t1
        t1->rt = treap_merge(t1->rt, t2);
        treap_pull(t1);
        return t1;
    } else {
        // make t1 the left child of t2
        t2->lt = treap_merge(t1, t2->lt);
        treap_pull(t2);
        return t2;
    }
}

inline pair<Treap*, Treap*> treap_split(Treap* tr, int sz) {
    if(tr == nullptr) return {nullptr, nullptr};

    int lsz = treap_sz(tr->lt);
    if(lsz + 1 == sz) {
        Treap* tmp = tr->rt;
        tr->rt = nullptr;
        treap_pull(tr);
        return {tr, tmp};
    } else if(lsz >= sz) {
        auto [l, r] = treap_split(tr->lt, sz);
        tr->lt = r;
        treap_pull(tr);
        return {l, tr};
    } else {
        auto [l, r] = treap_split(tr->rt, sz - lsz - 1);
        tr->rt = l;
        treap_pull(tr);
        return {tr, r};
    }
}

inline int leftmost_treap_item(Treap* tr) {
    if(tr == nullptr) return -1;
    if(tr->lt == nullptr) return tr->v;
    return leftmost_treap_item(tr->lt);
}

inline int _strict_upper_bound(Treap* tr, int v) {
    if(tr->lt == nullptr) return (tr->v > v ? 1 : 1 + _strict_upper_bound(tr->rt, v));

    if(tr->lt->mx > v) return _strict_upper_bound(tr->lt, v);
    else if(tr->v > v) return treap_sz(tr->lt) + 1;
    else return treap_sz(tr->lt) + 1 + _strict_upper_bound(tr->rt, v);
}

inline int strict_upper_bound(Treap* tr, int v) {
    if(tr == nullptr) return 0;
    if(tr->mx <= v) return 0;
    return _strict_upper_bound(tr, v);
}

inline int find_item(Treap* tr, int i) {
    assert(tr != nullptr);
    int lsz = treap_sz(tr->lt);

    if(lsz == i - 1) return tr->v;
    if(lsz >= i) return find_item(tr->lt, i);
    return find_item(tr->rt, i - lsz - 1);
}

Treap* treapify(const vi& a) {
    Treap* res = nullptr;
    for(int v : a) {
        res = treap_merge(res, new Treap(v));
    }

    return res;
}

struct query {
    int qt, qi, i;
};

typedef vector<query> vq;

pair<bool, Treap*> shuffle_tr(Treap* tr) {
    int n = treap_sz(tr);

    auto [l, r] = treap_split(tr, n >> 1);

    bool done_shuffling = l->mx < leftmost_treap_item(r);

    if(done_shuffling) return {done_shuffling, treap_merge(l, r)};

    Treap* res = nullptr;

    while(l != nullptr && r != nullptr) {
        int lv = leftmost_treap_item(l), rv = leftmost_treap_item(r);

        if(lv < rv) {
            // slice off from the left

            int lsp_sz = strict_upper_bound(l, rv) - 1;

            if(lsp_sz == -1) {
                // we're essentially done!
                res = treap_merge(res, l);
                l = nullptr;
                break;
            } else {
                auto [tmpl, tmpr] = treap_split(l, lsp_sz);
                res = treap_merge(res, tmpl);
                l = tmpr;
            }
        } else {
            // slice off from the right

            int rsp_sz = strict_upper_bound(r, lv) - 1;

            if(rsp_sz == -1) {
                // we're essentially done!
                res = treap_merge(res, r);
                r = nullptr;
                break;
            } else {
                auto [tmpl, tmpr] = treap_split(r, rsp_sz);
                res = treap_merge(res, tmpl);
                r = tmpr;
            }
        }
    }

    if(l != nullptr) {
        res = treap_merge(res, l);
    }

    if(r != nullptr) {
        res = treap_merge(res, r);
    }

    return {false, res};
}

void _inorder_traverse(Treap* tr) {
    if(tr == nullptr) return;

    _inorder_traverse(tr->lt);
    cerr << tr->v << " ";
    _inorder_traverse(tr->rt);
}

void inorder_traverse(Treap* tr) {
    _inorder_traverse(tr);
    cerr << endl;
}

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

    int n, q;
    cin >> n >> q;

    vi a(n, 0);
    for(int& v : a) cin >> v;

    Treap* tr = treapify(a);

    // inorder_traverse(tr);

    // for(int i = 0 ; i < n; i++) {
    //     cerr << find_item(tr, i + 1) << " ";
    // }
    // cerr << endl;

    vq qs(q, {0, 0, 0});

    vi res(q, 0);

    for(int i = 0; i < q; i++) {
        cin >> qs[i].qt >> qs[i].qi;
        qs[i].i = i;
    }

    sort(qs.begin(), qs.end(), [](query q1, query q2) {return q1.qt < q2.qt;});

    int cur_qi = 0;
    int cur_t = 0;

    while(true) {
        while(cur_qi < q && qs[cur_qi].qt == cur_t) {
            res[qs[cur_qi].i] = find_item(tr, qs[cur_qi].qi);
            cur_qi++;
        }

        if(cur_qi == q) break;

        auto [is_done, new_tr] = shuffle_tr(tr);
        if(is_done) break;
        tr = new_tr;
        cur_t++;
    }

    while(cur_qi < q) {
        res[qs[cur_qi].i] = find_item(tr, qs[cur_qi].qi);
        cur_qi++;
    }

    for(int i = 0; i < q; i++) {
        cout << res[i] << "\n";
    }
    cout << flush;

    return 0;
}

/*
1, 3, 6, 10, 15, 2, 5, 9, 14, 17
*/

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