# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
118543 | 2019-06-19T07:56:19 Z | Plurm | Crayfish scrivener (IOI12_scrivener) | C++11 | 0 ms | 0 KB |
#include <bits/stdc++.h> using namespace std; const int MXN = 1 << 20; const int COEFF = 12; char mem[COEFF*MXN]; int llink[COEFF*MXN]; int rlink[COEFF*MXN]; int root; int nodesz; vector<int> rootlist; vector<int> lens; inline int newnode(int o = -1){ int c = ++nodesz; if(o != -1){ llink[c] = llink[o]; rlink[c] = rlink[o]; mem[c] = mem[o]; } return c; } inline int build(int l, int r){ int c = newnode(); if(l == r) return c; int k = (l+r)/2; llink[c] = build(l,k); rlink[c] = build(k+1,r); return c; } inline int update(int& o, int& idx, char& upd, int& lb, int& rb){ int nr = newnode(o); int b = nr; while(lb != rb){ int k = (lb + rb)/2; if(idx <= k){ rb = k; llink[nr] = newnode(llink[nr]); nr = llink[nr]; }else{ lb = k+1; rlink[nr] = newnode(rlink[nr]); nr = rlink[nr]; } } mem[nr] = upd; return b; } inline char query(int& c, int& idx, int& lb, int& rb){ while(lb != rb){ int k = (lb + rb)/2; if(idx <= k){ rb = k; c = llink[c]; }else{ lb = k+1; c = rlink[c]; } } return mem[c]; } void Init() { root = build(0, MXN-1); rootlist.push_back(root); lens.push_back(0); } void TypeLetter(char L) { int l = lens.back(); int o = rootlist.back(); int c = update(o, l, L, 0, MXN-1); rootlist.push_back(c); lens.push_back(l+1); } void UndoCommands(int U) { int vn = rootlist.size() - 1 - U; lens.push_back(lens[vn]); rootlist.push_back(rootlist[vn]); } char GetLetter(int P) { return query(rootlist.back(), P, 0, MXN-1); }