Submission #256252

#	Time	Username	Problem	Language	Result	Execution time	Memory
256252		StevenH	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	517 ms	209144 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
struct Node
{
  int l, r;
  char c;
} node[maxn * 30];
int len[maxn], root[maxn];
int cnt = 0, v = 0;
int clone(int x)
{
  node[++cnt] = node[x];
  return cnt;
}
void build(int &u, int x, int y)
{
  u = ++cnt;
  if (x == y)
    return;
  int mid = (x + y) >> 1;
  build(node[u].l, x, mid);
  build(node[u].r, mid + 1, y);
  return;
}
void update(int &u, int x, int y, int pos, char c)
{
  u = clone(u);
  if (x == y)
  {
    node[u].c = c;
    return;
  }
  int mid = (x + y) >> 1;
  if (pos <= mid)
    update(node[u].l, x, mid, pos, c);
  else
    update(node[u].r, mid + 1, y, pos, c);
  return;
}
int query(int u, int x, int y, int pos)
{
  if (x == y)
    return u;
  int mid = (x + y) >> 1;
  if (pos <= mid)
    return query(node[u].l, x, mid, pos);
  else
    return query(node[u].r, mid + 1, y, pos);
}
void Init()
{
  cnt = 0;
  build(root[0], 1, 1000000);
  len[0] = 0;
  return;
}

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

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

char GetLetter(int P)
{
  int ans = query(root[v], 1, 1000000, P + 1);
  return node[ans].c;
}

// int main()
// {
//   Init();

//   int cmd_num;
//   int tmp = scanf("%d", &cmd_num);
//   assert(tmp == 1);

//   int i;
//   for (i = 0; i < cmd_num; i++)
//   {
//     char cmd;
//     scanf(" %c", &cmd);
//     if (cmd == 'T')
//     {
//       char letter;
//       tmp = scanf(" %c", &letter);
//       TypeLetter(letter);
//     }
//     else if (cmd == 'U')
//     {
//       int number;
//       tmp = scanf("%d", &number);
//       UndoCommands(number);
//     }
//     else if (cmd == 'P')
//     {
//       int index;
//       char letter;
//       tmp = scanf("%d", &index);
//       letter = GetLetter(index + 1);
//       printf("%c\n", letter);
//     }
//   }

//   // puts("Let's test for cheating!!");

//   return 0;
// }

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