#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define lc (i << 1)
#define rc (i << 1 | 1)
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int MN = 1e6 + 5, LN = 17, MOD = 1e9 + 7, INF = 0x3f3f3f3f, BSZ = 320;
char s[MN];
int spt[MN][21], dep[MN];
int cur;
void Init() {
}
// simiulate it as a tree, append on to previous node
void TypeLetter(char L) {
cur++;
s[cur] = L;
spt[cur][0] = cur - 1;
dep[cur] = dep[cur - 1] + 1;
for (int j = 1; j < LN; j++)
spt[cur][j] = spt[spt[cur][j - 1]][j - 1];
}
// undo will also act as an append, we go back U additions (therefore including all the undos as well)
// we can delete everything in the subtree by readding it to its parent
void UndoCommands(int U) {
int last = cur - U;
cur++;
s[cur] = s[last];
int par = spt[last][0];
spt[cur][0] = par;
dep[cur] = dep[par] + 1;
for (int j = 1; j < LN; j++)
spt[cur][j] = spt[spt[cur][j - 1]][j - 1];
}
char GetLetter(int P) {
P++;
int dis = dep[cur] - P;
int now = cur;
for (int j = LN - 1; j >= 0; j--)
if (dis - (1 << j) >= 0) {
now = spt[now][j];
dis -= (1 << j);
}
return s[now];
}
/*
int main() {
Init();
TypeLetter('a');
TypeLetter('b');
cout << GetLetter(1) << '\n';
TypeLetter('d');
UndoCommands(2);
UndoCommands(1);
cout << GetLetter(2) << '\n';
TypeLetter('e');
UndoCommands(1);
UndoCommands(5);
TypeLetter('c');
cout << GetLetter(2) << '\n';
UndoCommands(2) ;
cout << GetLetter(2) << '\n';
}
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
4 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 |
4 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 |
4 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 |
384 KB |
Output is correct |
2 |
Correct |
4 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 |
4 ms |
384 KB |
Output is correct |
8 |
Correct |
4 ms |
384 KB |
Output is correct |
9 |
Correct |
4 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 |
512 KB |
Output is correct |
2 |
Correct |
6 ms |
640 KB |
Output is correct |
3 |
Correct |
6 ms |
640 KB |
Output is correct |
4 |
Correct |
6 ms |
768 KB |
Output is correct |
5 |
Correct |
7 ms |
640 KB |
Output is correct |
6 |
Correct |
6 ms |
768 KB |
Output is correct |
7 |
Correct |
6 ms |
640 KB |
Output is correct |
8 |
Correct |
6 ms |
768 KB |
Output is correct |
9 |
Correct |
6 ms |
768 KB |
Output is correct |
10 |
Correct |
6 ms |
768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
345 ms |
62680 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
481 ms |
57848 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |