Submission #1096803

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096803		tosivanmak	Abracadabra (CEOI22_abracadabra)	C++17	100 / 100	702 ms	77216 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long


struct qry{
    ll t,i,qid;
    bool operator<(const qry& qr)const{
        if(t!=qr.t)return t<qr.t;
        if(i!=qr.i)return i<qr.i;
        return qid<qr.qid;
    }
};
struct SEG{
  vector<pair<ll,ll> >seg;
    vector<ll>cnt;
    ll _n;
    void init(ll n){
        _n=n;
        seg.resize(4*n+5);
        cnt.resize(4*n+5,0);
    }
    void upd(ll ul, ll l, ll r, pair<ll,ll>val, ll id){
        if(l==r){
            seg[id]=val;
            cnt[id]=val.second-val.first+1;
            return;
        }
        ll mid=(l+r)>>1;
        if(ul<=mid) upd(ul,l,mid,val,id*2);
        else upd(ul,mid+1,r,val,id*2+1);
        cnt[id]=cnt[id*2]+cnt[id*2+1];
    }
    ll bs(ll l, ll r, ll k, ll id){
        if(l==r) return l;
        ll mid=(l+r)>>1;
        if(cnt[id*2]>=k) return bs(l,mid,k,id*2);
        else return bs(mid+1,r,k-cnt[id*2],id*2+1);
    }
    pair<ll,ll> pairfinding(ll ul, ll l, ll r, ll id){
        if(l==r){
            return seg[id];
        }
        else{
            ll mid=(l+r)>>1;
            if(ul<=mid){
                return pairfinding(ul,l,mid,id*2);
            }
            else return pairfinding(ul,mid+1,r,id*2+1);
        }
    }
    ll sum(ll ql, ll qr, ll l, ll r, ll id){
        if(l>qr||r<ql)return 0;
        if(l>=ql&&r<=qr)return cnt[id];
        ll mid=(l+r)>>1;
        return sum(ql,qr,l,mid,id*2)+sum(ql,qr,mid+1,r,id*2+1);
    }
    ll find(){
        return bs(1,_n,_n/2+1,1);
    }
}st;
ll n;
ll nxt[200005];
ll a[200005];
void start_shuffle(){
   ll cur=st.find();
    ll tot=st.sum(1,cur,1,n,1);
    pair<ll,ll>rng=st.pairfinding(cur,1,n,1);
    ll rngsum=rng.second-rng.first+1;
    if(tot-rngsum==n/2) return;
    tot-=rngsum;
    ll diff=n/2-tot;
    pair<ll,ll>bruh={rng.first,rng.first+diff-1};
    st.upd(cur,1,n,bruh,1);
    ll curid=bruh.second+1;
    while(1){
        if(nxt[curid]>rng.second){
            st.upd(a[curid],1,n,{curid,rng.second},1);break;
        }
        else{
            st.upd(a[curid],1,n,{curid,nxt[curid]-1},1);
            curid=nxt[curid];
        }
    }
}
ll find_id(ll idd){
    ll cur=st.bs(1,n,idd,1);
    pair<ll,ll>rng=st.pairfinding(cur,1,n,1);
    ll tot=st.sum(1,cur,1,n,1);
    ll rngsum=rng.second-rng.first+1;
    tot-=rngsum;
    return a[rng.first+idd-tot-1];
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll q;
    cin>>n>>q;
    st.init(n);
    for(int i=1;i<=n;i++)cin>>a[i];
    vector<qry>qrs;
    int cnt=1;
    while(q--){
        ll t,i;
        cin>>t>>i;
        t=min(t,n);
        qrs.push_back({t,i,cnt});
        cnt++;
    }
    sort(qrs.begin(),qrs.end());
    ll shuffles=0;
    ll ans[qrs.size()+5];
    ll newarr[n+5];
    newarr[0]=0;
    for(int i=1;i<=n;i++){
        newarr[i]=max(newarr[i-1],a[i]);
    }
    ll ptr=1;
    for(int i=1;i<=n;i++){
        if(newarr[i]!=newarr[i-1]){
            st.upd(newarr[i-1],1,n,{ptr,i-1},1);
            ptr=i;
        }
    }
    st.upd(newarr[n],1,n,{ptr,n},1);

    stack<pair<ll,ll> >s;
    for(int i=1;i<=n;i++){
        while(s.size()){
            if(a[i]>s.top().second){
               nxt[s.top().first]=i; s.pop(); 
            }
            else break;
        }
        s.push({i,a[i]});
    }
    while(s.size()){
        nxt[s.top().first]=300000;
        s.pop();
    }
    for(int i=0;i<qrs.size();i++){
        while(shuffles<qrs[i].t){
            shuffles++;
            start_shuffle();
        }
        ans[qrs[i].qid]=find_id(qrs[i].i);
    }
    for(int i=1;i<=cnt-1;i++){
        cout<<ans[i]<<'\n';
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:141:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<qry>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |     for(int i=0;i<qrs.size();i++){
      |                 ~^~~~~~~~~~~

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