oj.uz

Submission #256251

# Submission time Handle Problem Language Result Execution time Memory
256251 2020-08-02T12:15:23 Z StevenH Crayfish scrivener (IOI12_scrivener) C++14
0 / 100
 417 ms 175736 KB 
#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);
  return node[ans].c;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 23808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 23808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 24192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 343 ms 175736 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 417 ms 153980 KB Output isn't correct
2 Halted 0 ms 0 KB -