#include <bits/stdc++.h>
#define N 1000050
#define log 22
using namespace std;
int n, id;
struct node
{
char c;
node *anc[log];
int sz;
node()
{
for(int i = 0; i < log ; i++) anc[i] = NULL;
sz = 0;
}
};
node *tree[N];
void TypeLetter(char c)
{
int tmp = ++id;
if(!tree[tmp]) tree[tmp] = new node();
tree[tmp]->c = c;
tree[tmp]->anc[0] = tree[tmp - 1];
for(int i = 1; i < log; i++)
{
(tree[tmp]->anc[i]) = (tree[tmp]->anc[i - 1] ? (tree[tmp]->anc[i - 1])->anc[i - 1] : NULL);
}
tree[tmp]->sz = tree[tmp - 1]->sz + 1;
}
void UndoCommands(int k)
{
int tmp = ++id;
tree[tmp] = tree[tmp - k - 1];
}
char GetLetter(int k)
{
int tmp = id;
node *root = tree[tmp];
int up = root->sz - k - 1;
for(int i = log - 1; i >= 0; i--)
{
if(up - (1<<i) >= 0)
{
up -= (1<<i);
root = root->anc[i];
}
}
return root->c;
}
void Init()
{
id = 0;
tree[0] = new node();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
256 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
4 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
4 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
640 KB |
Output is correct |
2 |
Correct |
6 ms |
640 KB |
Output is correct |
3 |
Correct |
6 ms |
768 KB |
Output is correct |
4 |
Correct |
6 ms |
1024 KB |
Output is correct |
5 |
Correct |
7 ms |
768 KB |
Output is correct |
6 |
Correct |
6 ms |
1152 KB |
Output is correct |
7 |
Correct |
6 ms |
1152 KB |
Output is correct |
8 |
Correct |
6 ms |
896 KB |
Output is correct |
9 |
Correct |
6 ms |
1024 KB |
Output is correct |
10 |
Correct |
6 ms |
768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
495 ms |
124284 KB |
Output is correct |
2 |
Correct |
568 ms |
140920 KB |
Output is correct |
3 |
Correct |
473 ms |
138872 KB |
Output is correct |
4 |
Correct |
452 ms |
112340 KB |
Output is correct |
5 |
Correct |
512 ms |
120952 KB |
Output is correct |
6 |
Correct |
535 ms |
152696 KB |
Output is correct |
7 |
Correct |
454 ms |
76536 KB |
Output is correct |
8 |
Correct |
499 ms |
113804 KB |
Output is correct |
9 |
Correct |
611 ms |
155768 KB |
Output is correct |
10 |
Correct |
298 ms |
114552 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
639 ms |
106104 KB |
Output is correct |
2 |
Correct |
696 ms |
97376 KB |
Output is correct |
3 |
Correct |
481 ms |
107384 KB |
Output is correct |
4 |
Correct |
441 ms |
81440 KB |
Output is correct |
5 |
Correct |
467 ms |
116728 KB |
Output is correct |
6 |
Correct |
463 ms |
109940 KB |
Output is correct |
7 |
Correct |
470 ms |
117120 KB |
Output is correct |
8 |
Correct |
601 ms |
58104 KB |
Output is correct |
9 |
Correct |
704 ms |
100728 KB |
Output is correct |
10 |
Correct |
293 ms |
113528 KB |
Output is correct |