Submission #1239373

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239373		caacrugon	Crayfish scrivener (IOI12_scrivener)	C++20	100 / 100	308 ms	185228 KiB

scrivener

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

#define mkp make_pair

vector<char> segtree(1000010*20,' ');
vector<int> lef(1000010*20),righ(1000010*20),root(1000010),siz(1000010);
int i=1,v=0;

void update(int exr, int newr, int l, int r, int x, char j){
  lef[newr]=lef[exr];
  righ[newr]=righ[exr];
  segtree[newr]=segtree[exr];
  if(l==r){
    segtree[newr]=j;
    return;
  }
  int m=l+((r-l)/2);
  if(x<=m){
    i++;
    lef[newr]=i;
    update(lef[exr],lef[newr],l,m,x,j);
  }else{
    i++;
    righ[newr]=i;
    update(righ[exr],righ[newr],m+1,r,x,j);
  }
}

char query(int root, int l, int r, int x){
  if(l==r)return segtree[root];
  int m=l+((r-l)/2);
  if(x<=m)return query(lef[root],l,m,x);
  else return query(righ[root],m+1,r,x);
}

void Init() {
  v=0;
  root[v]=v;
  siz[v]=v;
  v++;
}

void TypeLetter(char L) {
  i++;
  root[v]=i;
  siz[v]=siz[v-1]+1;
  update(root[v-1],root[v],0,1000000,siz[v-1],L);
  v++;
}

void UndoCommands(int U) {
  int target=v-1-U;
  root[v]=root[target];
  siz[v]=siz[target];
  v++;
}

char GetLetter(int P) {
  return query(root[v-1],0,1000000,P);
}

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