Submission #1266834

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266834		dosts	Abracadabra (CEOI22_abracadabra)	C++20	100 / 100	515 ms	57608 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e9;

const int N = 1e5+1;


struct ST {
    vi t;

    ST(int nn) {
        t.assign(4*nn+1,0);
    }

    void update(int node,int l,int r,int p,int v) {
        if (l == r) {
            t[node] = v;
            return;
        }
        int m = (l+r) >> 1;
        if (p <= m) update(2*node,l,m,p,v);
        else update(2*node+1,m+1,r,p,v);
        t[node] = t[2*node]+t[2*node+1];
    }

    int walk(int node,int l,int r,int x) {
        if (t[node] < x) assert(0);
        if (l == r) return l;
        int m = (l+r) >> 1;
        if (t[2*node] >= x) return walk(2*node,l,m,x);
        return walk(2*node+1,m+1,r,x-t[2*node]);
    }


    int query(int node,int l,int r,int L,int R) {
        if (l > R || r < L) return 0;
        if (l >= L && r <= R) return t[node];
        int m = (l+r) >> 1;
        return query(2*node,l,m,L,R)+query(2*node+1,m+1,r,L,R);
    }

};

void solve() {
    int n,q;
    cin >> n >> q;
    vi a(n+1);
    for (int i=1;i<=n;i++) cin >> a[i];
    using Query = pii;
    vector<Query> queries[n+1];
    vi ans(q+1);
    for (int i=1;i<=q;i++) {
        int t,p;
        cin >> t >> p;
        t = min(t,n);
        queries[t].push_back({p,i});
    }
    vi pos(n+1);
    for (int i=1;i<=n;i++) pos[a[i]] = i;
    vi R(n+1);
    stack<int> stk;
    for (int i = n;i>=1;i--) {
        while (!stk.empty() && a[stk.top()] < a[i]) stk.pop();
        if (stk.empty()) R[i] = n+1;
        else R[i] = stk.top();
        stk.push(i);
    }
    for (auto it : queries[0]) ans[it.ss] = a[it.ff];
    ST st(n);   
    st.update(1,1,n,a[1],n/2);
    st.update(1,1,n,a[n/2+1],n/2);

    auto fix = [&](int v) -> void {
        int cur = pos[v],curv = v;
        while (1) {
            int nxt = R[cur];
            int mine = st.query(1,1,n,curv,curv);
            if (nxt > cur+mine-1) break;
            st.update(1,1,n,curv,nxt-cur);
            st.update(1,1,n,a[nxt],mine-(nxt-cur));
            cur = nxt,curv = a[nxt];
        }
    };

    fix(a[1]);
    fix(a[n/2+1]);
    auto riffle = [&]() -> void {
        int w = st.walk(1,1,n,n/2);
        if (st.query(1,1,n,1,w) == n/2) return;
        //w ile başlayan block kesilir.
        int prv = st.query(1,1,n,1,w-1);
        int mine = st.query(1,1,n,w,w);
        int nxtt = a[pos[w]+n/2-prv];
        st.update(1,1,n,nxtt,mine-(n/2-prv));
        st.update(1,1,n,w,n/2-prv);
        fix(w);
        fix(nxtt);
    };
    for (int i=0;i<n;i++) {
        if (i) riffle();
        for (auto it : queries[i+1]) {
            int w = st.walk(1,1,n,it.ff);
            ans[it.ss] = a[pos[w]+(it.ff-st.query(1,1,n,1,w-1))-1];
        }
    }
    for (int i=1;i<=q;i++) cout << ans[i] << '\n';
} 

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifdef Dodi
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
}

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