#include <bits/stdc++.h>
using namespace std;
const int n = 1e6;
struct node {
char c;
node *l, *r;
node(char c) : c(c), l(0), r(0) {}
node(node *l, node *r) : c(0), l(l), r(r) {}
};
node *build(int b=0, int e=n-1)
{
if (b == e) return new node(0);
int m = (b+e)/2;
return new node(build(b, m), build(m+1, e));
}
node *update(int i, char c, node *p, int b=0, int e=n-1)
{
if (b==e) return new node(c);
int m = (b+e)/2;
if (i <= m)
return new node(update(i, c, p->l, b, m), p->r);
else
return new node(p->l, update(i, c, p->r, m+1, e));
}
char get(int i, node *p, int b=0, int e=n-1)
{
if (b == e) return p->c;
int m = (b+e)/2;
if (i <= m)
return get(i, p->l, b, m);
else
return get(i, p->r, m+1, e);
}
const int V = 1e6+1;
int vc = 0;
int len[V];
node *ptr[V];
void Init() {
//printf("Init()\n");
len[0] = 0;
ptr[0] = build();
}
void TypeLetter(char L) {
//printf("TypeLetter(%c)\n", L);
++vc;
len[vc] = len[vc-1]+1;
ptr[vc] = update(len[vc-1], L, ptr[vc-1]);
}
void UndoCommands(int U)
{
//printf("UndoCommands(%d)\n", U);
U = min(U, vc);
++vc;
len[vc] = len[vc-U-1];
ptr[vc] = ptr[vc-U-1];
}
char GetLetter(int P)
{
char ans = get(P, ptr[vc]);
//printf("GetLetter(%d) = %c\n", P, ans);
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
122 ms |
62968 KB |
Output is correct |
2 |
Correct |
121 ms |
63016 KB |
Output is correct |
3 |
Correct |
118 ms |
63136 KB |
Output is correct |
4 |
Correct |
132 ms |
63136 KB |
Output is correct |
5 |
Correct |
124 ms |
63180 KB |
Output is correct |
6 |
Correct |
106 ms |
63180 KB |
Output is correct |
7 |
Correct |
116 ms |
63228 KB |
Output is correct |
8 |
Correct |
117 ms |
63296 KB |
Output is correct |
9 |
Correct |
114 ms |
63380 KB |
Output is correct |
10 |
Correct |
109 ms |
63380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
119 ms |
63396 KB |
Output is correct |
2 |
Correct |
153 ms |
63460 KB |
Output is correct |
3 |
Correct |
101 ms |
63528 KB |
Output is correct |
4 |
Correct |
106 ms |
63528 KB |
Output is correct |
5 |
Correct |
100 ms |
63528 KB |
Output is correct |
6 |
Correct |
105 ms |
63528 KB |
Output is correct |
7 |
Correct |
102 ms |
63528 KB |
Output is correct |
8 |
Correct |
108 ms |
63548 KB |
Output is correct |
9 |
Correct |
103 ms |
63548 KB |
Output is correct |
10 |
Correct |
103 ms |
63548 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
109 ms |
64412 KB |
Output is correct |
2 |
Correct |
113 ms |
64552 KB |
Output is correct |
3 |
Correct |
105 ms |
64684 KB |
Output is correct |
4 |
Correct |
113 ms |
65532 KB |
Output is correct |
5 |
Correct |
104 ms |
65532 KB |
Output is correct |
6 |
Correct |
113 ms |
66096 KB |
Output is correct |
7 |
Correct |
105 ms |
66120 KB |
Output is correct |
8 |
Correct |
112 ms |
66120 KB |
Output is correct |
9 |
Correct |
110 ms |
66120 KB |
Output is correct |
10 |
Correct |
124 ms |
66120 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1091 ms |
263168 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1033 ms |
263168 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |