Submission #1235554

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235554		tapilyoca	Abracadabra (CEOI22_abracadabra)	C++20	75 / 100	3041 ms	188328 KiB

Main

/***********************************************
* auth: tapilyoca                              *
* date: 07/07/2025 at 22:42:20                 *
* dots: https://github.com/tapilyoca/dotilyoca * 
***********************************************/
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9+7;

template<typename T>
using vec = vector<T>;
using ll = long long;
using vll = vec<ll>;
using vvll = vec<vll>;
using pll = pair<ll,ll>;
using str = string;
#define pb push_back
#define dbg(x) if(1) cerr << #x << ": " << x << endl;

/***********************************************/

struct Segment {
    ll front, sstart, send, size;
    
    Segment() : sstart(0), send(0), front(0), size(0) {}

    Segment(ll s, ll e, ll f) {
        sstart = s;
        send = e;
        front = f;
        size = e-s+1;
    }

    bool operator>(const Segment&two) const {
        if(front == two.front) {
            if(sstart == two.sstart) {
                return send > two.send;
            }
            return sstart > two.sstart;
        }
        return front > two.front;
    }

    bool operator<(const Segment&two) const {
        if(front == two.front) {
            if(sstart == two.sstart) {
                return send < two.send;
            }
            return sstart<two.sstart;
        }
        return front < two.front;
    }

    bool operator==(const Segment&two) const {
        return front == two.front and sstart==two.sstart and send==two.send and size==two.size;
    }

    void print() {
        cerr << front << ": (" << sstart << ", " << send << ") ";
    }
};

struct Segtree {
    ll l, r;
    Segtree *lt, *rt;
    Segment val;
    ll sum;

    void combine() {
        sum = lt->sum + rt->sum;
    }
    
    Segtree(ll left, ll right, vec<Segment>&a) {
        sum = 0ll;
        l = left;
        r = right;
        lt = rt = nullptr;
        
        if(l == r) {
            val = a[l];
            return;
        }
        ll m = (l+r)>>1;
        lt = new Segtree(l,m,a);
        rt = new Segtree(m+1,r,a);
    }

    void activate(ll i, ll b) {
        if(i < l or r < i) return;
        if(i == l and l == r) {
            sum += val.size * b;
            return;
        }
        lt->activate(i,b);
        rt->activate(i,b);
        combine();
    }

    ll query_sum(ll ql, ll qr) {
        if(qr < l or r < ql) return 0;
        if(ql <= l and r <= qr) return sum;
        return lt->query_sum(ql,qr) + rt->query_sum(ql,qr);
    }

    void preorder() {
        if(lt) {
            lt->preorder();
            rt->preorder();
        } else {
            val.print();
        }
    }
};

ll walk(ll x, Segtree* root, Segtree* st) {
    if(st->l == st->r) {
        // cerr << "Found it for " << x << " on segment ";
        // st->val.print();
        // cerr << endl;

        ll lt_cover = (st->l == 0 ? 0 : root->query_sum(0,st->l - 1));
        ll leftover = x - lt_cover;
        ll og_index = leftover + st->val.sstart;

        // cerr << "Left covers the first " << lt_cover << endl;
        return og_index;
    }

    ll lt_cover = root->query_sum(0,st->lt->r);
    if(lt_cover > x) {
        return walk(x, root, st->lt);
    } else {
        return walk(x, root, st->rt);
    }
}

struct Query {
    ll t, x;

    Query() : t(0), x(0) {}

    Query(ll tt, ll xx) {
        t = tt;
        x = xx;
    }

    bool operator>(const Query&two) const {
        return t > two.t;
    }
    bool operator<(const Query&two) const {
        return t < two.t;
    }
};

vll riffle(vll &at) {
    vll a, b;
    ll n = at.size();

    for(int i = 0; i < n/2; i++) {
        a.pb(at[i]);
    }

    for(int j = n/2; j < n; j++) {
        b.pb(at[j]);
    }

    vll out;
    ll lp = 0, rp = 0;
    while(lp != n/2 and rp != n/2) {
        if(a[lp] < b[rp]) {
            out.pb(a[lp]);
            lp++;
        } else {
            out.pb(b[rp]);
            rp++;
        }
    }

    for(int i = lp; i < n/2; i++) out.pb(a[i]);
    for(int i = rp; i < n/2; i++) out.pb(b[i]);

    return out;
}

inline vll segmentize(vll &a) {
    ll n = a.size();

    stack<pll> st;

    vll out(n,1e18);
    for(int i = n-1; i >= 0; i--) {
        while(!st.empty() and st.top().first < a[i]) st.pop();
        if(!st.empty()) out[i] = st.top().second;
        // cerr << i << " " << out[i] << endl;
        st.push({a[i],i}); 
    }

    return out;
}


void solve() {
    ll n, q;
    cin >> n >> q;
    
    vll state(n,0);
    
    for(int i = 0; i < n; i++) {
        cin >> state[i];
    }    

    ll T = -1;

    vec<pair<Query,ll>> queries(q);
    vll ans(q,0);
    for(int i = 0; i < q; i++) {
        ll a, b;
        cin >> a >> b;
        b--;
        queries[i] = {Query(a,b),i};
        T = max(T,a);
    } sort(queries.begin(),queries.end());

    T += 2;

    vll stateTwo = riffle(state);
    vll next_seg = segmentize(stateTwo);

    // for(auto [qx,i] : queries) {
    //     cerr << qx.t << " " << qx.x << " " << i << endl;
    // }

    ll query_pointer = 0;

    while(query_pointer < q and queries[query_pointer].first.t < 2) {
        if(queries[query_pointer].first.t == 0) {
            ans[queries[query_pointer].second] = state[queries[query_pointer].first.x];            
        } else {
            ans[queries[query_pointer].second] = stateTwo[queries[query_pointer].first.x];
        }
        query_pointer++;
    }


    set<Segment> curr_state;
    set<Segment> all_states_evers;

    for(ll at = 0; at != 1e18; at = next_seg[at]) {
        ll one = at;
        ll two = (next_seg[at] == 1e18 ? n-1 : next_seg[at] - 1);
        curr_state.insert(Segment(one,two,stateTwo[at]));
        all_states_evers.insert(Segment(one,two,stateTwo[at]));
    }



    ll state_size = n;

    for(int shuffles = 1; shuffles <= T; shuffles++) {
        // dbg(shuffles);
        while(state_size > n/2) {
            if(state_size - (*prev(curr_state.end())).size < n/2) break;
            all_states_evers.insert(*prev(curr_state.end()));
            state_size -= (*prev(curr_state.end())).size;
            curr_state.erase(prev(curr_state.end()));
            // cerr << "hee hee hee haw" << endl;
        }

        if(state_size == n/2) break;

        // get the middle seg
        Segment midSeg = *curr_state.rbegin();
        curr_state.erase(prev(curr_state.end()));
        ll newSS = state_size - midSeg.size;

        curr_state.insert(Segment(midSeg.sstart, midSeg.sstart + (n/2 - newSS) - 1, midSeg.front));
        all_states_evers.insert(Segment(midSeg.sstart, midSeg.sstart + (n/2 - newSS) - 1, midSeg.front));
        
        // resegment it
        for(ll at = midSeg.sstart + (n/2 - newSS); at <= midSeg.send; at = next_seg[at]) {
            ll one = at;
            ll two = (next_seg[at] > midSeg.send ? midSeg.send : next_seg[at] - 1);
            curr_state.insert(Segment(one,two,stateTwo[at]));
            all_states_evers.insert(Segment(one,two,stateTwo[at]));
        }
    }


    while(!curr_state.empty()) {
        all_states_evers.insert(*prev(curr_state.end()));
        curr_state.erase(prev(curr_state.end()));
    }

    vec<Segment> all_states_ever(all_states_evers.begin(), all_states_evers.end());

    map<Segment,ll> seg_to_index;
    for(int i = 0; i < all_states_ever.size(); i++) {
        seg_to_index[all_states_ever[i]] = i;
    }

    Segtree st(0,all_states_ever.size()-1,all_states_ever);
    // cerr << "Segtree created." << endl;


    for(ll at = 0; at != 1e18; at = next_seg[at]) {
        ll one = at;
        ll two = (next_seg[at] == 1e18 ? n-1 : next_seg[at] - 1);
        curr_state.insert({one,two,stateTwo[at]});
        st.activate(seg_to_index[{one,two,stateTwo[at]}],1);
        // cerr << "Activated: " << stateTwo[at] << ": " << one << " " << two << endl;
    }

    // cerr << "Initialized" << endl;

    state_size = n;

    for(int shuffles = 1; shuffles <= T; shuffles++) {
        if(query_pointer == q) break;
        while(state_size > n/2) {
            if(state_size - (*prev(curr_state.end())).size < n/2) break;
            state_size -= (*prev(curr_state.end())).size;
            curr_state.erase(prev(curr_state.end()));
        }

        if(state_size == n/2) break;

        // get the middle seg
        Segment midSeg = *curr_state.rbegin();
        st.activate(seg_to_index[*prev(curr_state.end())],-1);

        curr_state.erase(prev(curr_state.end()));
        ll newSS = state_size - midSeg.size;

        curr_state.insert({midSeg.sstart, midSeg.sstart + (n/2 - newSS) - 1, midSeg.front});
        st.activate(seg_to_index[{midSeg.sstart, midSeg.sstart + (n/2 - newSS) - 1, midSeg.front}],1);

        // resegment it
        for(ll at = midSeg.sstart + (n/2 - newSS); at <= midSeg.send; at = next_seg[at]) {
            ll one = at;
            ll two = (next_seg[at] > midSeg.send ? midSeg.send : next_seg[at] - 1);
            curr_state.insert({one,two,stateTwo[at]});
            st.activate(seg_to_index[{one,two,stateTwo[at]}],1);
        }


        while(query_pointer < q and shuffles + 1 == queries[query_pointer].first.t) {
            ll ogdex = walk(queries[query_pointer].first.x, &st, &st);
            ans[queries[query_pointer].second] = stateTwo[ogdex];
            query_pointer++;
        }
    }


    while(query_pointer < q) {
        ll ogdex = walk(queries[query_pointer].first.x, &st, &st);
        // dbg(ogdex)
        ans[queries[query_pointer].second] = stateTwo[ogdex];
        query_pointer++;
    }

    for(int i = 0; i < q; i++) {
        cout << ans[i] << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;

    while(t--) {
        solve();
    }

    return 0;
}

/*

7 5 2 8 4 3 6 1 9 10 
3 6 1 7 5 2 8 4 9 10 
2 3 6 1 7 5 8 4 9 10 
[2] [3] [5] [6 1] [7] [8 4] [9] [10] 

2 1 4 5 6 3 


*/

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