#include <bits/stdc++.h>
using namespace std;
using pic = pair<int, char>;
const int N = 1<<20;
const int LN = 20;
int cnt;
char chr[N];
int len[N];
int par[N][LN];
int ptr[N];
inline int link(int p, char c)
{
chr[++cnt] = c;
par[cnt][0] = p;
len[cnt] = len[p]+1;
for (int i = 1; i < LN; ++i)
par[cnt][i] = par[par[cnt][i-1]][i-1];
return cnt;
}
void Init() {
//printf("Init()\n");
}
int vc;
void TypeLetter(char L) {
//printf("TypeLetter(%c)\n", L);
++vc;
ptr[vc] = link(ptr[vc-1], L);
}
void UndoCommands(int U)
{
//printf("UndoCommands(%d)\n", U);
U = min(U, vc);
++vc;
ptr[vc] = ptr[vc-U-1];
}
char GetLetter(int P)
{
int u = ptr[vc];
P = len[ptr[vc]]-P-1;
for (int i = LN-1; i >= 0; --i)
if ((1<<i)&P) u = par[u][i];
//printf("GetLetter(%d) = %c\n", P, ans);
return chr[u];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
488 KB |
Output is correct |
3 |
Correct |
3 ms |
544 KB |
Output is correct |
4 |
Correct |
3 ms |
544 KB |
Output is correct |
5 |
Correct |
2 ms |
544 KB |
Output is correct |
6 |
Correct |
3 ms |
592 KB |
Output is correct |
7 |
Correct |
3 ms |
652 KB |
Output is correct |
8 |
Correct |
4 ms |
652 KB |
Output is correct |
9 |
Correct |
3 ms |
652 KB |
Output is correct |
10 |
Correct |
4 ms |
664 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
664 KB |
Output is correct |
2 |
Correct |
3 ms |
664 KB |
Output is correct |
3 |
Correct |
3 ms |
664 KB |
Output is correct |
4 |
Correct |
4 ms |
664 KB |
Output is correct |
5 |
Correct |
3 ms |
664 KB |
Output is correct |
6 |
Correct |
2 ms |
664 KB |
Output is correct |
7 |
Correct |
3 ms |
664 KB |
Output is correct |
8 |
Correct |
2 ms |
664 KB |
Output is correct |
9 |
Correct |
3 ms |
664 KB |
Output is correct |
10 |
Correct |
3 ms |
696 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
832 KB |
Output is correct |
2 |
Correct |
4 ms |
840 KB |
Output is correct |
3 |
Correct |
4 ms |
868 KB |
Output is correct |
4 |
Correct |
4 ms |
968 KB |
Output is correct |
5 |
Correct |
6 ms |
968 KB |
Output is correct |
6 |
Correct |
6 ms |
1200 KB |
Output is correct |
7 |
Correct |
4 ms |
1200 KB |
Output is correct |
8 |
Correct |
3 ms |
1200 KB |
Output is correct |
9 |
Correct |
3 ms |
1200 KB |
Output is correct |
10 |
Correct |
4 ms |
1200 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
634 ms |
52036 KB |
Output is correct |
2 |
Correct |
776 ms |
57308 KB |
Output is correct |
3 |
Correct |
560 ms |
57308 KB |
Output is correct |
4 |
Correct |
524 ms |
57308 KB |
Output is correct |
5 |
Correct |
602 ms |
57308 KB |
Output is correct |
6 |
Correct |
399 ms |
62168 KB |
Output is correct |
7 |
Correct |
545 ms |
62168 KB |
Output is correct |
8 |
Correct |
515 ms |
62168 KB |
Output is correct |
9 |
Correct |
874 ms |
63508 KB |
Output is correct |
10 |
Correct |
246 ms |
63508 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
865 ms |
63508 KB |
Output is correct |
2 |
Correct |
908 ms |
63508 KB |
Output is correct |
3 |
Correct |
514 ms |
63508 KB |
Output is correct |
4 |
Correct |
519 ms |
63508 KB |
Output is correct |
5 |
Correct |
530 ms |
63508 KB |
Output is correct |
6 |
Correct |
664 ms |
63508 KB |
Output is correct |
7 |
Correct |
642 ms |
63508 KB |
Output is correct |
8 |
Correct |
897 ms |
63508 KB |
Output is correct |
9 |
Correct |
967 ms |
63508 KB |
Output is correct |
10 |
Correct |
257 ms |
63508 KB |
Output is correct |