#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1e6+6, maxk = 20;
struct Node
{
Node* par[maxk];
char c;
int len;
Node(char cc = '#', Node *p = NULL) {
c = cc;
par[0] = p;
len = p == NULL ? 0 : p->len + 1;
for (int k = 1; k < maxk; k++) {
if (par[k-1] == NULL) break;
par[k] = par[k-1]->par[k-1];
}
}
};
string s(Node *test) {
string s;
while (test != NULL) {
s = s + test->c;
test = test->par[0];
}
reverse(s.begin(),s.end());
return s;
}
Node* nodes[maxn];
int q;
void Init() {
q = 0;
nodes[q++] = new Node();
}
void TypeLetter(char L) {
nodes[q] = new Node(L,nodes[q-1]);
q++;
//cout << q << ": " << s(nodes[q-1]) << '\n';
}
void UndoCommands(int U) {
nodes[q] = nodes[q-U-1];
q++;
//cout << q << ": " << s(nodes[q-1]) << '\n';
}
char GetLetter(int P) {
Node *curr = nodes[q-1];
P = curr->len - 1 - P;
for (int k = maxk-1; k >= 0; k--) {
if (1<<k <= P) {
P -= 1<<k;
curr = curr->par[k];
}
}
//cout << s(nodes[q-1]) << '\n';
return curr->c;
}
/*
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';
}
*/
# |
결과 |
실행 시간 |
메모리 |
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 |
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 |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
404 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 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 |
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 |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
632 KB |
Output is correct |
2 |
Correct |
3 ms |
632 KB |
Output is correct |
3 |
Correct |
3 ms |
632 KB |
Output is correct |
4 |
Correct |
3 ms |
888 KB |
Output is correct |
5 |
Correct |
4 ms |
760 KB |
Output is correct |
6 |
Correct |
4 ms |
1016 KB |
Output is correct |
7 |
Correct |
4 ms |
1016 KB |
Output is correct |
8 |
Correct |
3 ms |
888 KB |
Output is correct |
9 |
Correct |
3 ms |
888 KB |
Output is correct |
10 |
Correct |
3 ms |
628 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
593 ms |
109496 KB |
Output is correct |
2 |
Correct |
694 ms |
121084 KB |
Output is correct |
3 |
Correct |
440 ms |
119264 KB |
Output is correct |
4 |
Correct |
419 ms |
97144 KB |
Output is correct |
5 |
Correct |
484 ms |
104312 KB |
Output is correct |
6 |
Correct |
517 ms |
131192 KB |
Output is correct |
7 |
Correct |
468 ms |
66780 KB |
Output is correct |
8 |
Correct |
552 ms |
98300 KB |
Output is correct |
9 |
Correct |
672 ms |
133752 KB |
Output is correct |
10 |
Correct |
254 ms |
98828 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
668 ms |
94436 KB |
Output is correct |
2 |
Correct |
799 ms |
84396 KB |
Output is correct |
3 |
Correct |
407 ms |
92664 KB |
Output is correct |
4 |
Correct |
443 ms |
71016 KB |
Output is correct |
5 |
Correct |
520 ms |
100600 KB |
Output is correct |
6 |
Correct |
520 ms |
94928 KB |
Output is correct |
7 |
Correct |
555 ms |
101184 KB |
Output is correct |
8 |
Correct |
609 ms |
50920 KB |
Output is correct |
9 |
Correct |
717 ms |
87108 KB |
Output is correct |
10 |
Correct |
269 ms |
98032 KB |
Output is correct |