Submission #851986

#	Time	Username	Problem	Language	Result	Execution time	Memory
851986		12345678	Crayfish scrivener (IOI12_scrivener)	C++17	34 / 100	361 ms	262144 KiB

scrivener

#include <bits/stdc++.h>

using namespace std;

const int nx=1e6+5;
int cnt[nx], t;

struct persist
{
  struct node
  {
    node *l, *r;
    char c=' ';
    node(char c): l(0), r(0), c(c){}
  };
  typedef node* pnode;
  pnode rt[nx];
  void build(int l, int r, pnode &t)
  {
    t=new node(' ');
    if (l==r) return;
    int md=(l+r)/2;
    build(l, md, t->l);
    build(md+1, r, t->r);
  }
  void update(int l, int r, int idx, char ch, pnode &t, pnode k)
  {
    if (idx<l||r<idx) return void(t=k);
    if (l==r) return void(t=new node(ch));
    t=new node(' ');
    int md=(l+r)/2;
    if (idx<=md) update(l, md, idx, ch, t->l, k->l), t->r=k->r;
    else update(md+1, r, idx, ch, t->r, k->r), t->l=k->l;
  }
  char query(int l, int r, int idx, pnode t)
  {
    if (l==r) return t->c;
    int md=(l+r)/2;
    if (idx<=md) return query(l, md, idx, t->l);
    return query(md+1, r, idx, t->r);
  }
} s;

void Init() {
  s.build(1, nx-1, s.rt[0]);
}

void TypeLetter(char L) {
  t++; cnt[t]=cnt[t-1]+1;
  s.update(1, nx-1, cnt[t], L, s.rt[t], s.rt[t-1]);
}

void UndoCommands(int U) {
  t++;
  cnt[t]=cnt[max(t-U-1, 0)];
  s.rt[t]=s.rt[max(t-U-1, 0)];
}

char GetLetter(int P) {
  return s.query(1, nx-1, P+1, s.rt[t]);
}

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