#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;
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;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
88 ms |
94328 KB |
Output is correct |
2 |
Correct |
82 ms |
94328 KB |
Output is correct |
3 |
Correct |
84 ms |
94200 KB |
Output is correct |
4 |
Correct |
86 ms |
94412 KB |
Output is correct |
5 |
Correct |
84 ms |
94312 KB |
Output is correct |
6 |
Correct |
86 ms |
94328 KB |
Output is correct |
7 |
Correct |
85 ms |
94456 KB |
Output is correct |
8 |
Correct |
92 ms |
94328 KB |
Output is correct |
9 |
Correct |
85 ms |
94240 KB |
Output is correct |
10 |
Correct |
79 ms |
94236 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
96 ms |
94296 KB |
Output is correct |
2 |
Incorrect |
84 ms |
94200 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
213 ms |
190756 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
368 ms |
196724 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
218 ms |
191264 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |