Submission #1231137

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231137		sitablechair	Abracadabra (CEOI22_abracadabra)	C++20	25 / 100	3096 ms	24800 KiB

Main

#include <bits/stdc++.h>

#define ll long long
#define ldb long double
#define endl '\n'
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ForD(i,r,l) for(int i=r;i>=l;i--)
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (signed)x.size()
#define unq(x) x.resize(unique(all(x))-x.begin())
#define F "TASK"
#define fio freopen(F".INP","r",stdin);freopen(F".OUT","w",stdout);

#ifdef NCGM
#include"debug.h"
#else 
#define debug(...) "fr";
#endif

using namespace std;

const int N=2e5+3,INF=2e9;

int n,q,a[N],r[N],r1[N],siz[N];
int pf[N],ans[N];
pair<int,int> ski[N];
vector<int> v[N];
vector<pair<int,int>> qr[N];
stack<int> st;

int query(int p) {
    int idx=p;
    int ans=0;
    while(idx>0) {
        ans+=pf[idx];
        idx-=(idx&(-idx));
    }
    return ans;
}
void update(int u,int v) {
    int idx=u;
    while(idx<=n) {
        pf[idx]+=v;
        idx+=(idx&(-idx));
    }
}

pair<int,int> find_id(int x) {
    int ans=0;
    int l=0,cur=0;
    ForD(i,17,0) {
        if (l+(1<<i)<n && cur+pf[l+(1<<i)]<x) {
            l+=1<<i;
            cur+=pf[l];
        }
    }
    l++;
    int tmp=query(l);
    int sec=(tmp==x?siz[l]-1:x-tmp+siz[l]-1);

    return {l,sec};
}
void cunny(int x,int id) {
    if (id==0 || id>siz[x]-1) return;
    
    int tmp=v[ski[x].ff][ski[x].ss+id];
    update(tmp,siz[x]-id-siz[tmp]);
    update(x,id-siz[x]);
    siz[tmp]=siz[x]-id;
    siz[x]=id;
    if (r1[tmp]<siz[tmp]-1) cunny(tmp,r1[tmp]+1);
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> q;
    fill(r,r+n+1,n+1);
    For(i,1,n) cin >> a[i];
    ForD(i,n,1) {
        while(sz(st) && a[st.top()]<a[i]) st.pop();
        if (sz(st)) r[i]=st.top();
        st.push(i);
    }
    For(i,1,n) r1[a[i]]=(r[i]-i-1);
    int mx=0;
    For(i,1,n) {
        if (a[mx]<a[i]) {
            mx=i;
        }
        v[a[mx]].pb(a[i]);
    }
    For(i,1,n) {
        siz[i]=sz(v[i]);
        update(i,siz[i]);
        For(j,0,sz(v[i])-1) ski[v[i][j]]={i,j};
    }
    For(i,1,q) {
        int x,y;
        cin >> x >> y;
        if (x>n) qr[n+1].pb({i,y});
        else qr[x].pb({i,y});
    }
    int haha=0;
    while(true) {
        for(auto el: qr[haha]) {
            pair<int,int> idx=find_id(el.ss);
            ans[el.ff]=v[ski[idx.ff].ff][ski[idx.ff].ss+idx.ss]; 
        }
        pair<int,int> idx1=find_id(n/2);
        if (idx1.ss==siz[idx1.ff]-1) break;
        pair<int,int> idx=find_id(n/2+1);
        cunny(idx.ff,idx.ss);
        haha++; 
    }
    For(i,haha+1,n+1) {
        for(auto el: qr[i]) {
            pair<int,int> idx=find_id(el.ss);
            ans[el.ff]=v[ski[idx.ff].ff][ski[idx.ff].ss+idx.ss]; 
        }
    }
    For(i,1,q) cout << ans[i] << endl;
    // while(q--) {
    //     int v1,p;
    //     cin >> v1 >> p;
    //     if (v1==1) {
    //         pair<int,int> idx=find_id(p);
    //         cout << v[ski[idx.ff].ff][ski[idx.ff].ss+idx.ss] << endl;
    //     } else {
    //         if (p==n) continue;
    //         pair<int,int> idx=find_id(p+1);
    //         cunny(idx.ff,idx.ss);
    //     }
    // }
    return 0;
}

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