#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<=19;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<=19;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=19;i>=0;i--){
if (((1<<i)&ind)!=0)
cur=arr[cur].anc[i];
}
return arr[cur].c;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
84 ms |
94328 KB |
Output is correct |
2 |
Correct |
85 ms |
94196 KB |
Output is correct |
3 |
Correct |
85 ms |
94200 KB |
Output is correct |
4 |
Correct |
82 ms |
94328 KB |
Output is correct |
5 |
Correct |
86 ms |
94316 KB |
Output is correct |
6 |
Correct |
83 ms |
94204 KB |
Output is correct |
7 |
Correct |
85 ms |
94236 KB |
Output is correct |
8 |
Correct |
88 ms |
94300 KB |
Output is correct |
9 |
Correct |
83 ms |
94200 KB |
Output is correct |
10 |
Correct |
83 ms |
94216 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
82 ms |
94280 KB |
Output is correct |
2 |
Correct |
82 ms |
94236 KB |
Output is correct |
3 |
Correct |
84 ms |
94224 KB |
Output is correct |
4 |
Correct |
84 ms |
94252 KB |
Output is correct |
5 |
Correct |
83 ms |
94308 KB |
Output is correct |
6 |
Correct |
83 ms |
94304 KB |
Output is correct |
7 |
Correct |
83 ms |
94192 KB |
Output is correct |
8 |
Correct |
85 ms |
94288 KB |
Output is correct |
9 |
Correct |
74 ms |
94216 KB |
Output is correct |
10 |
Correct |
84 ms |
94200 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
90 ms |
94320 KB |
Output is correct |
2 |
Correct |
86 ms |
94352 KB |
Output is correct |
3 |
Correct |
81 ms |
94312 KB |
Output is correct |
4 |
Correct |
86 ms |
94336 KB |
Output is correct |
5 |
Correct |
84 ms |
94344 KB |
Output is correct |
6 |
Correct |
84 ms |
94332 KB |
Output is correct |
7 |
Correct |
84 ms |
94332 KB |
Output is correct |
8 |
Correct |
83 ms |
94408 KB |
Output is correct |
9 |
Correct |
84 ms |
94344 KB |
Output is correct |
10 |
Correct |
87 ms |
94336 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
662 ms |
100992 KB |
Output is correct |
2 |
Correct |
759 ms |
101824 KB |
Output is correct |
3 |
Correct |
561 ms |
102604 KB |
Output is correct |
4 |
Correct |
608 ms |
104184 KB |
Output is correct |
5 |
Correct |
595 ms |
102684 KB |
Output is correct |
6 |
Correct |
489 ms |
102440 KB |
Output is correct |
7 |
Execution timed out |
1054 ms |
103260 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
791 ms |
101840 KB |
Output is correct |
2 |
Correct |
806 ms |
102620 KB |
Output is correct |
3 |
Correct |
535 ms |
103076 KB |
Output is correct |
4 |
Correct |
563 ms |
101972 KB |
Output is correct |
5 |
Correct |
516 ms |
102496 KB |
Output is correct |
6 |
Correct |
510 ms |
102428 KB |
Output is correct |
7 |
Correct |
713 ms |
102608 KB |
Output is correct |
8 |
Execution timed out |
1040 ms |
101232 KB |
Time limit exceeded |
9 |
Halted |
0 ms |
0 KB |
- |