#include<bits/stdc++.h>
using namespace std;
#define maxn 2000005
int n,cur,sz;
int len[1000005], root[1000005];
vector<int> L, R;
vector<char> val;
int newnode() {
val.push_back('0');
L.push_back(0); R.push_back(0);
return sz++;
}
void build(int pos,int l,int r) {
if(l==r) return ;
int mid = (l+r)/2, t1, t2;
t1 = newnode(); t2 = newnode();
L[pos] = t1; R[pos] = t2;
build(L[pos],l,mid); build(R[pos],mid+1,r);
}
void upgrade(int pos,int last,int l,int r,int x,char temp) {
if(l==r) {
val[pos] = temp;
return ;
}
int mid = (l+r)/2;
if(x<=mid) {
L[pos] = newnode();
R[pos] = R[last];
upgrade(L[pos],L[last],l,mid,x,temp);
}
else {
L[pos] = L[last];
R[pos] = newnode();
upgrade(R[pos],R[last],mid+1,r,x,temp);
}
}
char query(int pos,int l,int r,int x) {
if(l==r) return val[pos];
int mid = (l+r)/2;
if(x<=mid) return query(L[pos],l,mid,x);
return query(R[pos],mid+1,r,x);
}
void Init() {
root[0] = newnode();
len[0] = -1;
build(root[0],0,1000000);
}
void TypeLetter(char L) {
cur++;
root[cur] = newnode();
len[cur] = len[cur-1] + 1;
upgrade(root[cur],root[cur-1],0,1000000,len[cur],L);
}
void UndoCommands(int U) {
cur++;
root[cur] = root[cur-U-1];
len[cur] = len[cur-U-1];
}
char GetLetter(int P) {
return query(root[cur],0,1000000,P);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
34628 KB |
Output is correct |
2 |
Correct |
26 ms |
34628 KB |
Output is correct |
3 |
Correct |
29 ms |
34628 KB |
Output is correct |
4 |
Correct |
19 ms |
34628 KB |
Output is correct |
5 |
Correct |
16 ms |
34628 KB |
Output is correct |
6 |
Correct |
26 ms |
34628 KB |
Output is correct |
7 |
Correct |
33 ms |
34628 KB |
Output is correct |
8 |
Correct |
16 ms |
34628 KB |
Output is correct |
9 |
Correct |
36 ms |
34628 KB |
Output is correct |
10 |
Correct |
19 ms |
34628 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
34628 KB |
Output is correct |
2 |
Correct |
23 ms |
34628 KB |
Output is correct |
3 |
Correct |
19 ms |
34628 KB |
Output is correct |
4 |
Correct |
39 ms |
34628 KB |
Output is correct |
5 |
Correct |
29 ms |
34628 KB |
Output is correct |
6 |
Correct |
26 ms |
34628 KB |
Output is correct |
7 |
Correct |
33 ms |
34628 KB |
Output is correct |
8 |
Correct |
29 ms |
34628 KB |
Output is correct |
9 |
Correct |
29 ms |
34628 KB |
Output is correct |
10 |
Correct |
26 ms |
34628 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
34628 KB |
Output is correct |
2 |
Correct |
23 ms |
34628 KB |
Output is correct |
3 |
Correct |
33 ms |
34628 KB |
Output is correct |
4 |
Correct |
23 ms |
34628 KB |
Output is correct |
5 |
Correct |
36 ms |
34628 KB |
Output is correct |
6 |
Correct |
29 ms |
34628 KB |
Output is correct |
7 |
Correct |
26 ms |
34628 KB |
Output is correct |
8 |
Correct |
23 ms |
34628 KB |
Output is correct |
9 |
Correct |
26 ms |
34628 KB |
Output is correct |
10 |
Correct |
23 ms |
34628 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
43 ms |
59204 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
36 ms |
59204 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |