Submission #749367

#	Time	Username	Problem	Language	Result	Execution time	Memory
749367		tosivanmak	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	942 ms	231104 KiB

scrivener

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#include<bits/stdc++.h>
using namespace std;
#define ll int

// TODO: global variables can be declared here
struct info{
   ll lver,rver;
};

    vector<info>seg[1048575];
   ll vernochar[1000001];
   ll versionofcommand[1000001];
   vector<char>opt[1000001];
   void build(ll l, ll r, ll id){
       if(l==r){
       return;
       }
       else{
           ll mid=(l+r)>>1;
           build(l,mid,id*2);
           build(mid+1,r,id*2+1);
           seg[id].push_back({0,0});
       }
   }
   char qry(ll version, ll ql, ll l, ll r, ll id){
       if(l==r){
           return opt[ql][version-1];
       }
       else{
       ll mid=(l+r)>>1;
       if(ql<=mid){
           return qry(seg[id][version].lver,ql,l,mid,id*2);
       }
       else{
           return qry(seg[id][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){
          opt[ul].push_back(app);
      }
      else{
          ll mid=(l+r)>>1;
          if(ul<=mid){
              upd(seg[id][version].lver,ul,l,mid,app,id*2);
              ll siz;
              if(l==mid){
                  siz=opt[ul].size();
              }
              else{
              siz=seg[id*2].size()-1;
              }
               seg[id].push_back({siz,seg[id][version].rver});
          }
          else{
              upd(seg[id][version].rver,ul,mid+1,r,app,id*2+1);
               ll siz;
                 if(mid+1==r){
                  siz=opt[ul].size();
              }
              else{
              siz=seg[id*2+1].size()-1;
              }
              seg[id].push_back({seg[id][version].lver,siz});
          }
      }
   }

ll curcom=1;
void Init() {
build(1,1000000,1);
vernochar[0]=0;
versionofcommand[0]=0;
}
 
void TypeLetter(char L){
  // TODO: implementation
  ll acccom=curcom-1;
  ll lol=versionofcommand[acccom];
  ll k=vernochar[lol];
  upd(lol,k+1,1,1000000,L,1);
  vernochar[seg[1].size()-1]=k+1; 
  versionofcommand[curcom]=seg[1].size()-1;
  curcom++;
}
 
void UndoCommands(int U){
  // TODO: implementation
  ll acccom=curcom-U-1;
  versionofcommand[curcom]=versionofcommand[acccom];
  curcom++;
}
 
char GetLetter(int P){
  // TODO: implementation
   ll version=versionofcommand[curcom-1];
//    cout<<version<<'\n';
   P++;
   return qry(version,P,1,1000000,1);
}

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