Submission #749329

#	Time	Username	Problem	Language	Result	Execution time	Memory
749329		tosivanmak	Crayfish scrivener (IOI12_scrivener)	C++17	74 / 100	925 ms	262144 KiB

scrivener

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


// TODO: global variables can be declared here
struct info{
   ll lver,rver;
};
struct SEG{
    vector<info>seg[524288*4];
   ll vernochar[1000001];
   ll versionofcommand[1000001];
   vector<vector<char> >opt;
   void init(){
       vector<char>lol;
       opt.push_back(lol);
   }
   void build(ll l, ll r, ll id){
       if(l==r){
       seg[id].push_back({0,0});
       }
       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){
          seg[id].push_back({0,0});
          if(opt.size()-1>=ul){
              opt[ul].push_back(app);
          }
          else{
              vector<char>lol;
              opt.push_back(lol);
              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=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=seg[id*2+1].size()-1;
              seg[id].push_back({seg[id][version].lver,siz});
          }
      }
   }
};
SEG st;
ll curcom=1;
void Init() {
    st.init();
    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].size()-1]=k+1; 
  st.versionofcommand[curcom]=st.seg[1].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);
}

Compilation message (stderr)

scrivener.cpp: In member function 'void SEG::upd(int, int, int, int, char, int)':
scrivener.cpp:47:26: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<char> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |           if(opt.size()-1>=ul){
      |              ~~~~~~~~~~~~^~~~

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