# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
246372 | 2020-07-09T01:00:37 Z | ant101 | Crayfish scrivener (IOI12_scrivener) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h> #define N 1000050 #define log 22 using namespace std; int n, id; struct node { char c; node *anc[log]; int sz; node() { for(int i = 0; i < log ; i++) anc[i] = NULL; sz = 0; } }; node *tree[N]; void TypeLetter(char c) { int tmp = ++id; if(!tree[tmp]) tree[tmp] = new node(); tree[tmp]->c = c; tree[tmp]->anc[0] = tree[tmp - 1]; for(int i = 1; i < log; i++) { (tree[tmp]->anc[i]) = (tree[tmp]->anc[i - 1] ? (tree[tmp]->anc[i - 1])->anc[i - 1] : NULL); } tree[tmp]->sz = tree[tmp - 1]->sz + 1; } void UndoCommands(int k) { int tmp = ++id; tree[tmp] = tree[tmp - k - 1]; } char GetLetter(int k) { int tmp = id; node *root = tree[tmp]; int up = root->sz - k - 1; for(int i = log - 1; i >= 0; i--) { if(up - (1<<i) >= 0) { up -= (1<<i); root = root->anc[i]; } } return root->c; } void Init() { id = 0; tree[0] = new node(); } int main() { ios::sync_with_stdio(false); cin.tie(0); cin>>n; tree[0] = new node(); while(n--) { char a, b; int c; cin>>a; if(a == 'T') { cin>>b; TypeLetter(b); } if(a == 'U') { cin>>c; UndoCommands(c); } if(a == 'P') { cin>>c; cout<<GetLetter(c)<<"\n"; } } }