#include <vector>
using namespace std;
const int MXN = 1 << 20;
const int COEFF = 16;
char mem[COEFF*MXN];
int llink[COEFF*MXN];
int rlink[COEFF*MXN];
int root;
int nodesz;
vector<int> rootlist;
vector<int> lens;
inline int newnode(int o = -1){
int c = ++nodesz;
if(o != -1){
llink[c] = llink[o];
rlink[c] = rlink[o];
mem[c] = mem[o];
}
return c;
}
inline int build(int l, int r){
int c = newnode();
if(l == r) return c;
int k = (l+r)/2;
llink[c] = build(l,k);
rlink[c] = build(k+1,r);
return c;
}
inline int update(int o, int idx, char upd, int lb, int rb){
int nr = newnode(o);
int b = nr;
while(lb != rb){
int k = (lb + rb)/2;
if(idx <= k){
rb = k;
llink[nr] = newnode(llink[nr]);
nr = llink[nr];
}else{
lb = k+1;
rlink[nr] = newnode(rlink[nr]);
nr = rlink[nr];
}
}
mem[nr] = upd;
return b;
}
inline char query(int c, int idx, int lb, int rb){
while(lb != rb){
int k = (lb + rb)/2;
if(idx <= k){
rb = k;
c = llink[c];
}else{
lb = k+1;
c = rlink[c];
}
}
return mem[c];
}
void Init() {
root = build(0, MXN-1);
rootlist.push_back(root);
lens.push_back(0);
}
void TypeLetter(char L) {
int l = lens.back();
int o = rootlist.back();
int c = update(o, l, L, 0, MXN-1);
rootlist.push_back(c);
lens.push_back(l+1);
}
void UndoCommands(int U) {
int vn = rootlist.size() - 1 - U;
lens.push_back(lens[vn]);
rootlist.push_back(rootlist[vn]);
}
char GetLetter(int P) {
return query(rootlist.back(), P, 0, MXN-1);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
16768 KB |
Output is correct |
2 |
Correct |
19 ms |
16768 KB |
Output is correct |
3 |
Correct |
20 ms |
16768 KB |
Output is correct |
4 |
Correct |
20 ms |
16768 KB |
Output is correct |
5 |
Correct |
20 ms |
16760 KB |
Output is correct |
6 |
Correct |
18 ms |
16768 KB |
Output is correct |
7 |
Correct |
18 ms |
16768 KB |
Output is correct |
8 |
Correct |
21 ms |
16760 KB |
Output is correct |
9 |
Correct |
19 ms |
16748 KB |
Output is correct |
10 |
Correct |
20 ms |
16768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
16768 KB |
Output is correct |
2 |
Correct |
21 ms |
16740 KB |
Output is correct |
3 |
Correct |
19 ms |
16760 KB |
Output is correct |
4 |
Correct |
19 ms |
16732 KB |
Output is correct |
5 |
Correct |
19 ms |
16760 KB |
Output is correct |
6 |
Correct |
19 ms |
16768 KB |
Output is correct |
7 |
Correct |
24 ms |
16760 KB |
Output is correct |
8 |
Correct |
20 ms |
16768 KB |
Output is correct |
9 |
Correct |
19 ms |
16768 KB |
Output is correct |
10 |
Correct |
20 ms |
16760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
17024 KB |
Output is correct |
2 |
Correct |
30 ms |
17020 KB |
Output is correct |
3 |
Correct |
21 ms |
17112 KB |
Output is correct |
4 |
Correct |
21 ms |
17408 KB |
Output is correct |
5 |
Correct |
21 ms |
17144 KB |
Output is correct |
6 |
Correct |
21 ms |
17536 KB |
Output is correct |
7 |
Correct |
20 ms |
17408 KB |
Output is correct |
8 |
Correct |
21 ms |
17408 KB |
Output is correct |
9 |
Correct |
20 ms |
17400 KB |
Output is correct |
10 |
Correct |
20 ms |
17144 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
350 ms |
129752 KB |
Output is correct |
2 |
Correct |
327 ms |
142208 KB |
Output is correct |
3 |
Correct |
356 ms |
139588 KB |
Output is correct |
4 |
Correct |
384 ms |
114284 KB |
Output is correct |
5 |
Correct |
447 ms |
123384 KB |
Output is correct |
6 |
Correct |
359 ms |
152700 KB |
Output is correct |
7 |
Correct |
437 ms |
82024 KB |
Output is correct |
8 |
Correct |
386 ms |
116456 KB |
Output is correct |
9 |
Execution timed out |
305 ms |
153552 KB |
Time limit exceeded (wall clock) |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
456 ms |
112824 KB |
Output is correct |
2 |
Correct |
544 ms |
100836 KB |
Output is correct |
3 |
Correct |
392 ms |
109900 KB |
Output is correct |
4 |
Correct |
444 ms |
85212 KB |
Output is correct |
5 |
Correct |
327 ms |
119244 KB |
Output is correct |
6 |
Correct |
344 ms |
113668 KB |
Output is correct |
7 |
Correct |
343 ms |
120260 KB |
Output is correct |
8 |
Correct |
472 ms |
64976 KB |
Output is correct |
9 |
Correct |
541 ms |
104092 KB |
Output is correct |
10 |
Correct |
257 ms |
117272 KB |
Output is correct |