#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <iomanip>
#include <deque>
#include <cassert>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <chrono>
#include <ctime>
#include <random>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#include <iterator>
#include <climits>
//#include "scrivener.h"
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001
#define MOD 1000000007
int root[1000001];
int nex,version;
struct node{
int child;
int length;
char c;
int anc[21];
node(){
child=-1;
length=0;
c='?';
for (int i=0;i<=20;i++)
anc[i]=-1;
}
};
node arr[1000001];
bool started=false;
void calcAnc(int ind){
arr[ind].anc[0]=arr[ind].child;
for (int i=1;i<=20;i++){
if (arr[ind].anc[i-1]==-1)
arr[ind].anc[i]=-1;
else
arr[ind].anc[i]=arr[arr[ind].anc[i-1]].anc[i-1];
}
}
void Init(){
}
void TypeLetter(char c){
if (!started){
root[0]=0;
arr[0].c=c;
arr[0].length=1;
nex++;
started=true;
return;
}
version++;
root[version]=nex;
arr[nex].length=arr[root[version-1]].length+1;
arr[nex].c=c;
arr[nex].child=root[version-1];
calcAnc(nex);
nex++;
}
void UndoCommands(int x){
version++;
root[version]=nex;
arr[nex].length=arr[root[version-x-1]].length;
arr[nex].c=arr[root[version-x-1]].c;
arr[nex].child=arr[root[version-x-1]].child;
calcAnc(nex);
nex++;
}
char GetLetter(int ind){
ind=arr[root[version]].length-1-ind;
int cur=root[version];
for (int i=20;i>=0;i--){
if (((1<<i)&ind)!=0)
cur=arr[cur].anc[i];
}
return arr[cur].c;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
93 ms |
94308 KB |
Output is correct |
2 |
Correct |
85 ms |
94200 KB |
Output is correct |
3 |
Correct |
86 ms |
94400 KB |
Output is correct |
4 |
Correct |
85 ms |
94220 KB |
Output is correct |
5 |
Correct |
85 ms |
94300 KB |
Output is correct |
6 |
Correct |
87 ms |
94200 KB |
Output is correct |
7 |
Correct |
84 ms |
94232 KB |
Output is correct |
8 |
Correct |
85 ms |
94316 KB |
Output is correct |
9 |
Correct |
83 ms |
94248 KB |
Output is correct |
10 |
Correct |
86 ms |
94196 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
81 ms |
94300 KB |
Output is correct |
2 |
Correct |
84 ms |
94296 KB |
Output is correct |
3 |
Correct |
86 ms |
94200 KB |
Output is correct |
4 |
Correct |
81 ms |
94312 KB |
Output is correct |
5 |
Correct |
85 ms |
94300 KB |
Output is correct |
6 |
Correct |
84 ms |
94220 KB |
Output is correct |
7 |
Correct |
86 ms |
94272 KB |
Output is correct |
8 |
Correct |
83 ms |
94264 KB |
Output is correct |
9 |
Correct |
83 ms |
94200 KB |
Output is correct |
10 |
Correct |
86 ms |
94200 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
84 ms |
94328 KB |
Output is correct |
2 |
Correct |
84 ms |
94376 KB |
Output is correct |
3 |
Correct |
85 ms |
94276 KB |
Output is correct |
4 |
Correct |
85 ms |
94328 KB |
Output is correct |
5 |
Correct |
84 ms |
94300 KB |
Output is correct |
6 |
Correct |
89 ms |
94324 KB |
Output is correct |
7 |
Correct |
85 ms |
94296 KB |
Output is correct |
8 |
Correct |
86 ms |
94280 KB |
Output is correct |
9 |
Correct |
85 ms |
94292 KB |
Output is correct |
10 |
Correct |
87 ms |
94324 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
684 ms |
101080 KB |
Output is correct |
2 |
Correct |
763 ms |
101876 KB |
Output is correct |
3 |
Correct |
548 ms |
102640 KB |
Output is correct |
4 |
Correct |
671 ms |
104232 KB |
Output is correct |
5 |
Correct |
577 ms |
102608 KB |
Output is correct |
6 |
Correct |
504 ms |
102288 KB |
Output is correct |
7 |
Execution timed out |
1012 ms |
101740 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
846 ms |
101856 KB |
Output is correct |
2 |
Correct |
806 ms |
102660 KB |
Output is correct |
3 |
Correct |
535 ms |
103160 KB |
Output is correct |
4 |
Correct |
551 ms |
104316 KB |
Output is correct |
5 |
Correct |
513 ms |
102648 KB |
Output is correct |
6 |
Correct |
518 ms |
102492 KB |
Output is correct |
7 |
Correct |
536 ms |
102616 KB |
Output is correct |
8 |
Execution timed out |
1054 ms |
103764 KB |
Time limit exceeded |
9 |
Halted |
0 ms |
0 KB |
- |