#include <bits/stdc++.h>
using namespace std;
struct node
{
int v, l, r;
char c;
};
int all, ver;
int root[1000100];
node seg[30000000];
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] = {0, L, R};
return now;
}
void Init() {
root[0] = build(1, 1000050);
}
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].v = 1;
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, seg[now].v = seg[L].v+seg[R].v;
return now;
}
void TypeLetter(char L) {
ver++;
root[ver] = update(root[ver-1], 1, 1000050, seg[root[ver-1]].v+1, L);
}
void UndoCommands(int U) {
ver++;
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, 1000050, P+1);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
31744 KB |
Output is correct |
2 |
Correct |
28 ms |
31616 KB |
Output is correct |
3 |
Correct |
28 ms |
31608 KB |
Output is correct |
4 |
Correct |
30 ms |
31608 KB |
Output is correct |
5 |
Correct |
28 ms |
31616 KB |
Output is correct |
6 |
Correct |
27 ms |
31744 KB |
Output is correct |
7 |
Correct |
28 ms |
31616 KB |
Output is correct |
8 |
Correct |
27 ms |
31616 KB |
Output is correct |
9 |
Correct |
28 ms |
31616 KB |
Output is correct |
10 |
Correct |
28 ms |
31744 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
31616 KB |
Output is correct |
2 |
Correct |
29 ms |
31744 KB |
Output is correct |
3 |
Correct |
30 ms |
31744 KB |
Output is correct |
4 |
Correct |
28 ms |
31736 KB |
Output is correct |
5 |
Correct |
27 ms |
31616 KB |
Output is correct |
6 |
Correct |
29 ms |
31744 KB |
Output is correct |
7 |
Correct |
29 ms |
31736 KB |
Output is correct |
8 |
Correct |
27 ms |
31616 KB |
Output is correct |
9 |
Correct |
29 ms |
31608 KB |
Output is correct |
10 |
Correct |
30 ms |
31736 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
31 ms |
32128 KB |
Output is correct |
2 |
Correct |
28 ms |
32128 KB |
Output is correct |
3 |
Correct |
31 ms |
32256 KB |
Output is correct |
4 |
Correct |
29 ms |
32636 KB |
Output is correct |
5 |
Correct |
29 ms |
32248 KB |
Output is correct |
6 |
Correct |
30 ms |
32896 KB |
Output is correct |
7 |
Correct |
31 ms |
32888 KB |
Output is correct |
8 |
Correct |
29 ms |
32512 KB |
Output is correct |
9 |
Correct |
30 ms |
32640 KB |
Output is correct |
10 |
Correct |
29 ms |
32128 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
433 ms |
224376 KB |
Output is correct |
2 |
Correct |
425 ms |
244088 KB |
Output is correct |
3 |
Correct |
445 ms |
239352 KB |
Output is correct |
4 |
Correct |
455 ms |
194424 KB |
Output is correct |
5 |
Correct |
490 ms |
211320 KB |
Output is correct |
6 |
Correct |
462 ms |
262144 KB |
Output is correct |
7 |
Correct |
455 ms |
137720 KB |
Output is correct |
8 |
Correct |
487 ms |
198136 KB |
Output is correct |
9 |
Runtime error |
457 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
524 ms |
194804 KB |
Output is correct |
2 |
Correct |
519 ms |
174200 KB |
Output is correct |
3 |
Correct |
462 ms |
188792 KB |
Output is correct |
4 |
Correct |
467 ms |
146172 KB |
Output is correct |
5 |
Correct |
421 ms |
204324 KB |
Output is correct |
6 |
Correct |
439 ms |
193400 KB |
Output is correct |
7 |
Correct |
443 ms |
204920 KB |
Output is correct |
8 |
Correct |
487 ms |
108440 KB |
Output is correct |
9 |
Correct |
550 ms |
178040 KB |
Output is correct |
10 |
Correct |
368 ms |
199416 KB |
Output is correct |