Submission #256247

#	Time	Username	Problem	Language	Result	Execution time	Memory
256247		StevenH	Crayfish scrivener (IOI12_scrivener)	C++14	0 / 100	434 ms	262148 KiB

scrivener

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

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