Submission #1078077

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078077		juicy	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	714 ms	86720 KiB

scrivener

#include <bits/stdc++.h>

const int N = 1e6 + 5, LG = 20;

int n;
char c[N];
int pr[LG][N], cnt[N];

void Init() {

}

void TypeLetter(char L) {
  c[++n] = L;
  pr[0][n] = n - 1;
  cnt[n] = cnt[n - 1] + 1;
  for (int j = 1; j < LG; ++j) {
    pr[j][n] = pr[j - 1][pr[j - 1][n]];
  }
}

void UndoCommands(int l) {
  ++n;
  pr[0][n] = n - l - 1;
  cnt[n] = cnt[n - l - 1];
  for (int j = 1; j < LG; ++j) {
    pr[j][n] = pr[j - 1][pr[j - 1][n]];
  }
}

char GetLetter(int p) {
  int u = n;
  for (int j = LG - 1; ~j; --j) {
    if (cnt[pr[j][u]] >= p + 1) {
      u = pr[j][u];
    }
  }
  return c[u];
}

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