#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;
int length[1000001];
char c[1000001];
int anc[1000001][20];
bool started=false;
void calcAnc(int ind){
for (int i=1;i<=19;i++){
if (anc[ind][i-1]==-1)
anc[ind][i]=-1;
else
anc[ind][i]=anc[anc[ind][i-1]][i-1];
}
}
void Init(){
for (int i=0;i<20;i++)
anc[0][i]=-1;
}
void TypeLetter(char ch){
if (!started){
root[0]=0;
c[0]=ch;
length[0]=1;
nex++;
started=true;
return;
}
version++;
root[version]=nex;
length[nex]=length[root[version-1]]+1;
c[nex]=ch;
anc[nex][0]=root[version-1];
calcAnc(nex);
nex++;
}
void UndoCommands(int x){
version++;
root[version]=nex;
length[nex]=length[root[version-x-1]];
c[nex]=c[root[version-x-1]];
anc[nex][0]=anc[root[version-x-1]][0];
calcAnc(nex);
nex++;
}
char GetLetter(int ind){
ind=length[root[version]]-1-ind;
int cur=root[version];
for (int i=19;i>=0;i--){
if (((1<<i)&ind)!=0)
cur=anc[cur][i];
}
return c[cur];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
3 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
1 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
0 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
372 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
504 KB |
Output is correct |
2 |
Correct |
3 ms |
632 KB |
Output is correct |
3 |
Correct |
12 ms |
680 KB |
Output is correct |
4 |
Correct |
4 ms |
760 KB |
Output is correct |
5 |
Correct |
4 ms |
632 KB |
Output is correct |
6 |
Correct |
4 ms |
760 KB |
Output is correct |
7 |
Correct |
3 ms |
632 KB |
Output is correct |
8 |
Correct |
4 ms |
760 KB |
Output is correct |
9 |
Correct |
4 ms |
760 KB |
Output is correct |
10 |
Correct |
0 ms |
760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
641 ms |
63404 KB |
Output is correct |
2 |
Correct |
931 ms |
80712 KB |
Output is correct |
3 |
Correct |
709 ms |
80952 KB |
Output is correct |
4 |
Correct |
794 ms |
85836 KB |
Output is correct |
5 |
Correct |
537 ms |
75024 KB |
Output is correct |
6 |
Correct |
484 ms |
87304 KB |
Output is correct |
7 |
Execution timed out |
1058 ms |
76976 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
722 ms |
61652 KB |
Output is correct |
2 |
Correct |
785 ms |
55132 KB |
Output is correct |
3 |
Correct |
506 ms |
68700 KB |
Output is correct |
4 |
Correct |
519 ms |
61640 KB |
Output is correct |
5 |
Correct |
506 ms |
78328 KB |
Output is correct |
6 |
Correct |
503 ms |
80760 KB |
Output is correct |
7 |
Correct |
530 ms |
80560 KB |
Output is correct |
8 |
Execution timed out |
1038 ms |
69784 KB |
Time limit exceeded |
9 |
Halted |
0 ms |
0 KB |
- |