제출 #1234610

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1234610		tapilyoca	Abracadabra (CEOI22_abracadabra)	C++20	40 / 100	779 ms	49500 KiB

Main

/***********************************************
* auth: tapilyoca                              *
* date: 07/07/2025 at 22:42:20                 *
* dots: https://github.com/tapilyoca/dotilyoca * 
***********************************************/

#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 {
        return front > two.front;
    }

    bool operator<(const Segment&two) const {
        return front < two.front;
    }

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

struct Query {
    ll t, x;

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

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

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 bruh(set<Segment> s) {
    for(auto itr = s.begin(); itr != s.end(); itr++) {
        Segment x = *itr;
        x.print();
    }
}

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<Query> queries(q);
    for(int i = 0; i < q; i++) {
        ll a, b;
        cin >> a >> b;
        b--;
        queries[i] = Query(a,b);
        T = a;
    }

    vll stateTwo = riffle(state);

    if(T == 0) {
        for(Query &q : queries) cout << state[q.x] << endl;
        return;
    } else if(T == 1) {
        for(Query &q : queries) cout << stateTwo[q.x] << endl;
        return;
    }

    vll next_seg = segmentize(stateTwo);


    set<Segment> curr_state;

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


    set<Segment> done_states;

    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;
            done_states.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()));
        // midSeg.print();

        ll newSS = state_size - midSeg.size;
        // dbg(newSS);
        // dbg(state_size);
        // dbg(midSeg.size);

        curr_state.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]));
        }

        // cerr << "end of " << shuffles << " have ";
        // bruh(curr_state);
        // cerr << endl;
    }

    // cerr << "State finalized" << endl;

    vll finalState;
    for(auto itr = done_states.begin(); itr != done_states.end(); itr++) {
        curr_state.insert(*itr);
    }

    
    while(!curr_state.empty()) {
        Segment coolbeans = *curr_state.begin();
        // coolbeans.print();
        curr_state.erase(curr_state.begin());
        for(ll i = coolbeans.sstart; i <= coolbeans.send; i++) finalState.pb(stateTwo[i]);
    }

    // cerr << "\nFinal state: ";
    // for(ll &x : finalState) cerr << x << " ";
    // cerr << endl;

    for(Query &q : queries) {
        cout << finalState[q.x] << 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 

*/

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