Submission #1232696

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232696		ProtonDecay314	Abracadabra (CEOI22_abracadabra)	C++20	0 / 100	846 ms	589824 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;

/*
Persistent Multiset data struct
*/
struct BTreap {
    BTreap *lt, *rt;
    int sz, v, pr; // size, value, and priority

    BTreap(BTreap* a_lt, BTreap* a_rt, int a_v): lt(a_lt), rt(a_rt), sz(1), v(a_v), pr(rnd.rand_int(0, numeric_limits<int>::max())) {
        if(lt != nullptr) sz += lt->sz;
        if(rt != nullptr) sz += rt->sz;
    }
};

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

/*
Merges two treaps together, respecting the BST and treap invariants
*/
BTreap* merge_btreap(BTreap* t1, BTreap* t2) {
    if(t1 == nullptr) return t2;
    if(t2 == nullptr) return t1;
    
    if(t1 != nullptr && t2 != nullptr) {
        if(t1->pr >= t2->pr) swap(t1, t2);
        if(t2->v > t1->v) {
            // make t2 the right child of t1
        
            return new BTreap(t1->lt, merge_btreap(t1->rt, t2), t1->v);
        } else {
            // make t2 the left child of t1

            return new BTreap(merge_btreap(t1->lt, t2), t1->rt, t1->v);
        }
    }
}

/*
Splits a treap into two, given the value v

left: <= v
right: > v
*/
pair<BTreap*, BTreap*> split_btreap(BTreap* tr, int v) {
    if(tr == nullptr) {
        return {nullptr, nullptr};
    }

    if(v == tr->v) {
        return {new BTreap(tr->lt, nullptr, tr->v), tr->rt};
    } else if (v > tr->v) {
        // split to the right
        if(tr->rt == nullptr) {
            return {tr, nullptr};
        } else {
            auto [lsplit, rsplit] = split_btreap(tr->rt, v);

            return {new BTreap(tr->lt, lsplit, tr->v), rsplit};
        }
    } else {
        // split to the left
        if(tr->lt == nullptr) {
            return {nullptr, tr};
        } else {
            auto [lsplit, rsplit] = split_btreap(tr->lt, v);
            
            return {lsplit, new BTreap(rsplit, tr->rt, tr->v)};
        }
    }
}

BTreap* insert(BTreap* tr, int v) {
    BTreap* nw = new BTreap(nullptr, nullptr, v);

    auto [lt, rt] = split_btreap(tr, v);
    
    return merge_btreap(merge_btreap(lt, nw), rt);
}

BTreap* _unify(BTreap* t1, BTreap* t2) {
    BTreap* res = t2;
    if(t1 == nullptr) return t2;
    if(t2 == nullptr) return t1;

    res = insert(res, t1->v);
    if(t1->lt != nullptr) res = _unify(t1->lt, res);
    if(t1->rt != nullptr) res = _unify(t1->rt, res);

    return res;
}

BTreap* unify(BTreap* t1, BTreap* t2) {
    if(btreap_sz(t1) > btreap_sz(t2)) swap(t1, t2);
    return _unify(t1, t2);
}

void _inorder_print_btreap(BTreap* root) {
    if(root == nullptr) {
        return;
    }

    cerr << "(";
    _inorder_print_btreap(root->lt);
    cerr << root->v;
    _inorder_print_btreap(root->rt);
    cerr << ")";
}

void inorder_print_btreap(BTreap* root) {
    _inorder_print_btreap(root);
    cerr << endl;
}

BTreap* btreapify(const vi& a) {
    BTreap* tr = nullptr;

    int n = a.size();

    for(int i = 0; i < n; i++) {
        tr = insert(tr, a[i]);
    }

    return tr;
}

int btreap_leq(BTreap* tr, int v) {
    if(tr == nullptr) return 0;
    if(tr->v <= v) return btreap_sz(tr->lt) + 1 + btreap_leq(tr->rt, v);
    else return btreap_leq(tr->lt, v);
}

int btreap_geq(BTreap* tr, int v) {
    if(tr == nullptr) return 0;
    if(tr->v >= v) return btreap_sz(tr->rt) + 1 + btreap_geq(tr->lt, v);
    else return btreap_geq(tr->rt, v);
}

/*
Treap of BSTs

Note: does not need to be persistent
*/

struct Treap {
    Treap *lt, *rt;
    BTreap *items;
    int v, pr;

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

Treap* make_treap_node(int v) {
    Treap* res = new Treap(v);

    res->items = new BTreap(nullptr, nullptr, v);
    
    return res;
}

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

inline Treap* treap_pull(Treap* tr) {
    if(tr == nullptr) return tr;

    tr->items = unify((tr->lt == nullptr ? nullptr : tr->lt->items), (tr->rt == nullptr ? nullptr : tr->rt->items));

    tr->items = insert(tr->items, tr->v);

    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 int leftmost_treap_item(Treap* tr) {
    if(tr == nullptr) return -1;
    if(tr->lt == nullptr) return tr->v;
    return leftmost_treap_item(tr->lt);
}

/*
returns two treaps, where the left treap has size sz
*/
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) {
        // split point is to the right
        auto [l, r] = treap_split(tr->rt, sz - lsz - 1);

        tr->rt = l;
        treap_pull(tr);
        return {tr, r};
    } else {
        // split point is to the left
        auto [l, r] = treap_split(tr->lt, sz);

        tr->lt = r;
        treap_pull(tr);
        return {l, tr};
    }
}

/*
finds the item at an index i (1-based)
*/

inline int find_item(Treap* tr, int i) {
    if(treap_sz(tr->lt) == i - 1) return tr->v;
    if(treap_sz(tr->lt) >= i) return find_item(tr->lt, i);
    return find_item(tr->rt, i - treap_sz(tr->lt) - 1);
}

/*
finds the first item greater than v
*/
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(btreap_geq(tr->lt->items, v + 1) > 0) return _strict_upper_bound(tr->lt, v);
    else if(tr->v > v) return btreap_sz(tr->lt->items) + 1;
    else return btreap_sz(tr->lt->items) + 1 + _strict_upper_bound(tr->rt, v);
}

int strict_upper_bound(Treap* tr, int v) {
    if(tr == nullptr) return 0;
    if(btreap_geq(tr->items, v + 1) == 0) return 0;
    return _strict_upper_bound(tr, v);
}

Treap* treapify(const vi& a) {
    // int n = a.size();

    Treap* res = nullptr;

    for(int v : a) {
        Treap* nw_node = make_treap_node(v);
        res = treap_merge(res, nw_node);
    }

    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 = btreap_geq(l->items, leftmost_treap_item(r)) == 0;

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

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);

    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
*/

Compilation message (stderr)

Main.cpp: In function 'BTreap* merge_btreap(BTreap*, BTreap*)':
Main.cpp:68:1: warning: control reaches end of non-void function [-Wreturn-type]
   68 | }
      | ^

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