This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
int curr, last=-1, h[1000006], pa[20][1000006];
char C[1000006];
void add(int x, char c){
last++;
pa[0][last]=curr;
h[last]=h[curr]+1;
curr=last;
C[curr]=c;
for (int i=1; i<20; i++){
pa[i][curr]=pa[i-1][pa[i-1][curr]];
}
}
void roll_back(int t){
curr=++last;
h[curr]=h[t];
C[curr]=C[t];
for (int i=0; i<20; i++){
pa[i][curr]=pa[i][t];
}
}
int Kth_parent(int k){
int Pa=curr;
for (int i=19; i>=0; i--){
if(k&(1<<i))Pa=pa[i][Pa];
}
return C[Pa];
}
void Init() { h[0]=-1; }
string s;
void TypeLetter(char L) { add(curr, L); }
void UndoCommands(int U) { roll_back(last-U); }
char GetLetter(int P) { return Kth_parent(h[curr]-P); }
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |