#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 |
4 ms |
384 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 |
4 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 |
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 |
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 |
4 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 |
4 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 |
6 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 |
7 ms |
1024 KB |
Output is correct |
10 |
Correct |
6 ms |
640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
526 ms |
127556 KB |
Output is correct |
2 |
Correct |
575 ms |
140920 KB |
Output is correct |
3 |
Correct |
455 ms |
138872 KB |
Output is correct |
4 |
Correct |
451 ms |
112348 KB |
Output is correct |
5 |
Correct |
504 ms |
121080 KB |
Output is correct |
6 |
Correct |
516 ms |
152508 KB |
Output is correct |
7 |
Correct |
485 ms |
76536 KB |
Output is correct |
8 |
Correct |
502 ms |
113912 KB |
Output is correct |
9 |
Correct |
587 ms |
155640 KB |
Output is correct |
10 |
Correct |
303 ms |
114552 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
633 ms |
109744 KB |
Output is correct |
2 |
Correct |
750 ms |
97452 KB |
Output is correct |
3 |
Correct |
435 ms |
107256 KB |
Output is correct |
4 |
Correct |
431 ms |
81528 KB |
Output is correct |
5 |
Correct |
455 ms |
116600 KB |
Output is correct |
6 |
Correct |
447 ms |
109944 KB |
Output is correct |
7 |
Correct |
484 ms |
117240 KB |
Output is correct |
8 |
Correct |
572 ms |
58104 KB |
Output is correct |
9 |
Correct |
677 ms |
100600 KB |
Output is correct |
10 |
Correct |
308 ms |
113528 KB |
Output is correct |