Submission #749313

#	Time	Username	Problem	Language	Result	Execution time	Memory
749313		tosivanmak	Crayfish scrivener (IOI12_scrivener)	C++17	34 / 100	801 ms	262144 KiB

scrivener

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


// TODO: global variables can be declared here
struct info{
   char c;
   ll lver,rver;
};
struct node{
    vector<info>ver;
};
struct SEG{
    vector<node>seg;
   ll vernochar[1000005];
   ll versionofcommand[1000005];
   void init(ll n){
       seg.resize(4*n+5);
   }
   void build(ll l, ll r, ll id){
       if(l==r){
       seg[id].ver.push_back({'-',0,0});
       }
       else{
           ll mid=(l+r)>>1;
           build(l,mid,id*2);
           build(mid+1,r,id*2+1);
           seg[id].ver.push_back({'-',0,0});
       }
   }
   char qry(ll version, ll ql, ll l, ll r, ll id){
       if(l==r){
           return seg[id].ver[version].c;
       }
       else{
       ll mid=(l+r)>>1;
       if(ql<=mid){
           return qry(seg[id].ver[version].lver,ql,l,mid,id*2);
       }
       else{
           return qry(seg[id].ver[version].rver,ql,mid+1,r,id*2+1);
       }
       }
   }
   void upd(ll version, ll ul, ll l, ll r, char app, ll id){
      if(l==r){
          seg[id].ver.push_back({app,0,0});
      }
      else{
          ll mid=(l+r)>>1;
          if(ul<=mid){
              upd(seg[id].ver[version].lver,ul,l,mid,app,id*2);
              ll siz=seg[id*2].ver.size()-1;
               seg[id].ver.push_back({'-',siz,seg[id].ver[version].rver});
          }
          else{
              upd(seg[id].ver[version].rver,ul,mid+1,r,app,id*2+1);
               ll siz=seg[id*2+1].ver.size()-1;
              seg[id].ver.push_back({'-',seg[id].ver[version].lver,siz});
          }
      }
   }
};
SEG st;
ll curcom=1;
void Init() {
    st.init(524288);
    st.build(1,1000000,1);
    st.vernochar[0]=0;
    st.versionofcommand[0]=0;
}

void TypeLetter(char L){
  // TODO: implementation
  ll acccom=curcom-1;
  ll lol=st.versionofcommand[acccom];
  ll k=st.vernochar[lol];
  st.upd(lol,k+1,1,1000000,L,1);
  st.vernochar[st.seg[1].ver.size()-1]=k+1; 
  st.versionofcommand[curcom]=st.seg[1].ver.size()-1;
  curcom++;
}

void UndoCommands(int U){
  // TODO: implementation
  ll acccom=curcom-U-1;
  st.versionofcommand[curcom]=st.versionofcommand[acccom];
  curcom++;
}

char GetLetter(int P){
  // TODO: implementation
   ll version=st.versionofcommand[curcom-1];
//    cout<<version<<'\n';
   P++;
   return st.qry(version,P,1,1000000,1);
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 22 / 22
• Subtask 4: 0 / 26
• Subtask 5: 0 / 40