#include <bits/stdc++.h>
using namespace std;
struct node
{
int l, r;
char c;
};
int all, ver;
int root[1000005], heigh[1000005];
node seg[23000000];
int build(int l, int r)
{
int now = ++all;
if(l == r) return now;
int mid = (l+r)>>1;
int L = build(l, mid), R = build(mid+1, r);
seg[now].l = L, seg[now].r = R;
return now;
}
void Init() {
root[0] = build(1, 1000000);
}
int update(int idx, int l, int r, int p, char c) {
if(!(l <= p && p <= r)) return idx;
int now = ++all;
if(l == r)
{
seg[now].c = c;
return now;
}
int mid = (l+r)>>1;
int L = update(seg[idx].l, l, mid, p, c), R = update(seg[idx].r, mid+1, r, p, c);
seg[now].l = L, seg[now].r = R;
return now;
}
void TypeLetter(char L) {
ver++;
heigh[ver] = heigh[ver-1]+1;
root[ver] = update(root[ver-1], 1, 1000000, heigh[ver], L);
}
void UndoCommands(int U) {
ver++;
heigh[ver] = heigh[ver-U-1];
root[ver] = root[ver-U-1];
}
char query(int idx, int l, int r, int p)
{
if(l == r) return seg[idx].c;
int mid = (l+r)>>1;
return (p <= mid) ? query(seg[idx].l, l, mid, p) : query(seg[idx].r, mid+1, r, p);
}
char GetLetter(int P) {
return query(root[ver], 1, 1000000, P+1);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
23808 KB |
Output is correct |
2 |
Correct |
24 ms |
23808 KB |
Output is correct |
3 |
Correct |
39 ms |
23800 KB |
Output is correct |
4 |
Correct |
23 ms |
23808 KB |
Output is correct |
5 |
Correct |
23 ms |
23808 KB |
Output is correct |
6 |
Correct |
24 ms |
23936 KB |
Output is correct |
7 |
Correct |
23 ms |
23800 KB |
Output is correct |
8 |
Correct |
23 ms |
23800 KB |
Output is correct |
9 |
Correct |
24 ms |
23808 KB |
Output is correct |
10 |
Correct |
28 ms |
23800 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
23808 KB |
Output is correct |
2 |
Correct |
24 ms |
23808 KB |
Output is correct |
3 |
Correct |
24 ms |
23800 KB |
Output is correct |
4 |
Correct |
23 ms |
23936 KB |
Output is correct |
5 |
Correct |
24 ms |
23824 KB |
Output is correct |
6 |
Correct |
23 ms |
23808 KB |
Output is correct |
7 |
Correct |
24 ms |
23808 KB |
Output is correct |
8 |
Correct |
26 ms |
23808 KB |
Output is correct |
9 |
Correct |
24 ms |
23808 KB |
Output is correct |
10 |
Correct |
23 ms |
23860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
24192 KB |
Output is correct |
2 |
Correct |
25 ms |
24312 KB |
Output is correct |
3 |
Correct |
26 ms |
24312 KB |
Output is correct |
4 |
Correct |
25 ms |
24568 KB |
Output is correct |
5 |
Correct |
30 ms |
24312 KB |
Output is correct |
6 |
Correct |
26 ms |
24832 KB |
Output is correct |
7 |
Correct |
25 ms |
24824 KB |
Output is correct |
8 |
Correct |
25 ms |
24568 KB |
Output is correct |
9 |
Correct |
25 ms |
24576 KB |
Output is correct |
10 |
Correct |
26 ms |
24280 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
406 ms |
174716 KB |
Output is correct |
2 |
Correct |
410 ms |
190204 KB |
Output is correct |
3 |
Correct |
424 ms |
186720 KB |
Output is correct |
4 |
Correct |
435 ms |
153208 KB |
Output is correct |
5 |
Correct |
462 ms |
165368 KB |
Output is correct |
6 |
Correct |
422 ms |
204024 KB |
Output is correct |
7 |
Correct |
442 ms |
110328 KB |
Output is correct |
8 |
Correct |
421 ms |
155768 KB |
Output is correct |
9 |
Correct |
453 ms |
207348 KB |
Output is correct |
10 |
Correct |
361 ms |
158712 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
462 ms |
152184 KB |
Output is correct |
2 |
Correct |
520 ms |
136568 KB |
Output is correct |
3 |
Correct |
425 ms |
148088 KB |
Output is correct |
4 |
Correct |
460 ms |
115576 KB |
Output is correct |
5 |
Correct |
402 ms |
160252 KB |
Output is correct |
6 |
Correct |
393 ms |
152160 KB |
Output is correct |
7 |
Correct |
410 ms |
160720 KB |
Output is correct |
8 |
Correct |
471 ms |
87800 KB |
Output is correct |
9 |
Correct |
520 ms |
140024 KB |
Output is correct |
10 |
Correct |
336 ms |
157212 KB |
Output is correct |