Submission #1111676

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111676		noyancanturk	Abracadabra (CEOI22_abracadabra)	C++17	100 / 100	1034 ms	47028 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
using pii=pair<int,int>;
struct query{
  int t,i,ind;
};

struct Node{
  int val,maxi,sz,pri;
  Node*l,*r;
  Node(int val):val(val),maxi(val),sz(1),pri(rand()),l(0),r(0){}
};

using pnode=Node*;

int getcnt(pnode p){
  if(p)return p->sz;
  return 0;
}
int getval(pnode p){
  if(p)return p->maxi;
  return 0;
}
void upd(pnode p){
  if(p){
    p->sz=getcnt(p->l)+getcnt(p->r)+1;
    p->maxi=p->val;
    if(p->l)p->maxi=max(p->maxi,p->l->maxi);
    if(p->r)p->maxi=max(p->maxi,p->r->maxi);
  }
}

void merge(pnode&p,pnode l,pnode r){
  if(!l){
    p=r;
    return;
  }
  if(!r){
    p=l;
    return;
  }
  if(l->pri<r->pri){
    merge(r->l,l,r->l);
    p=r;
  }else{
    merge(l->r,l->r,r);
    p=l;
  }
  upd(p);
}

void splitind(pnode p,pnode&l,pnode&r,int ind){
  if(!p){
    l=r=0;
    return;
  }
  if(getcnt(p->l)+1<ind){
    splitind(p->r,p->r,r,ind-getcnt(p->l)-1);
    l=p;
  }else{
    splitind(p->l,l,p->l,ind);
    r=p;
  }
  upd(p);
}

void split(pnode p,pnode&l,pnode&r,int val){
  if(!p){
    l=r=0;
    return;
  }
  if(max(p->val,getval(p->l))<=val){
    split(p->r,p->r,r,val);
    l=p;
  }else{
    split(p->l,l,p->l,val);
    r=p;
  }
  upd(p);
}

int find(pnode p,int ind){
  if(ind==getcnt(p->l)+1)return p->val;
  if(ind<getcnt(p->l)+1)return find(p->l,ind);
  return find(p->r,ind-getcnt(p->l)-1);
}
int beg(pnode p){
  if(p->l)return beg(p->l);
  return p->val;
}
pnode last(pnode p){
  if(p->r)return last(p->r);
  return p;
}

void walk(pnode p){
  if(!p)return;
  walk(p->l);
  //cerr<<p->val<<' ';
  walk(p->r);
}

int main(){
  #ifdef Local
  freopen(".in","r",stdin);
  freopen(".out","w",stdout);
  #endif
  int n,m;
  cin>>n>>m;
  int a[n];
  pnode t1=0,t2=0;
  for(int i=0;i<n;i++){
    cin>>a[i];
    if(i<n/2)merge(t1,t1,new Node(a[i]));
    else merge(t2,t2,new Node(a[i]));
  }
  query q[m];
  for(int i=0;i<m;i++){
    cin>>q[i].t>>q[i].i;
    q[i].ind=i;
  }
  sort(q,q+m,[&](query x,query y)->bool {
    return x.t<y.t;
  });
  bool done=0;
  int turn=0;
  int ans[m];
  for(int i=0;i<m;i++){
    while(turn<q[i].t&&!done){
      done=1;
      turn++;
      bool cont;
      //cerr<<"begin\n";
      do{
        cont=0;
      //cerr<<"begin again\n";
        int val=beg(t2);
        //cerr<<"found\n";
        pnode p1=0,p2=0;
        split(t1,p1,p2,val);
        if(p2!=0){
          cont=1;
          done=0;
          pnode p3=0;
        //cerr<<"sp beg\n";
          split(t2,p3,t2,val);
          merge(t1,p1,p3);
          merge(t1,t1,p2);
        //cerr<<"sp end\n";
        }
        //cerr<<"here\n";
      }while(cont&&getcnt(t2));
      //cerr<<"end\n";
      while(n/2<getcnt(t1)){
        pnode p=0;
        splitind(t1,t1,p,n/2+1);
        merge(t2,p,t2);
      }
      //cerr<<"check\n";
    }
    //walk(t1);cerr<<'\n';walk(t2);
    //cerr<<'\n';
    if(q[i].i<=n/2){
      ans[q[i].ind]=find(t1,q[i].i);
    }else{
      //cerr<<q[i].i-n/2<<" huh\n";
      ans[q[i].ind]=find(t2,q[i].i-n/2);
    }
  //cerr<<"ok\n";
  //cerr<<ans[q[i].ind]<<'\n';
  }
  for(int i:ans)cout<<i<<'\n';
}

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