Submission #249468

#	Time	Username	Problem	Language	Result	Execution time	Memory
249468		kai824	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	589 ms	86844 KiB

scrivener

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

int depth[1000005],parent[1000005][20],cur=0;
char t[1000005];

void Init(){
  for(int i=0;i<20;i++)parent[0][i]=-1;
  depth[0]=0;
}

void TypeLetter(char l){
  cur++;
  t[cur]=l;
  depth[cur]=depth[cur-1]+1;
  parent[cur][0]=cur-1;
  for(int i=1;i<20;i++){
    if(parent[cur][i-1]==-1)parent[cur][i]=-1;
    else parent[cur][i]=parent[parent[cur][i-1] ][i-1];
  }
}

void UndoCommands(int u){
  cur++;
  for(int i=0;i<20;i++){
    parent[cur][i]=parent[cur-1-u][i];
  }
  t[cur]=t[cur-u-1];
  depth[cur]=depth[cur-u-1];
}

char GetLetter(int p){
  int up=depth[cur]-1-p,node=cur;
  for(int i=19;i>=0;i--){
    if((1<<i)<=up){
      up-=(1<<i);
      node=parent[node][i];
    }
  }
  return t[node];
}

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