#include<bits/stdc++.h>
using namespace std;
#define maxn 1000005
struct node{
char val;
node* l;
node* r;
};
int n,cur;
int sz[maxn];
node* root[maxn];
void build(node* pos,int l,int r) {
if(l==r) return ;
int mid = (l+r)/2;
pos->l = new node; pos->r = new node;
build(pos->l,l,mid); build(pos->r,mid+1,r);
}
void upgrade(node* pos,node* last,int l,int r,int x,int val) {
if(l==r) {
pos->val = val;
return ;
}
int mid = (l+r)/2;
if(x<=mid) {
pos->l = new node;
pos->r = last->r;
upgrade(pos->l,last->l,l,mid,x,val);
}
else {
pos->l = last->l;
pos->r = new node;
upgrade(pos->r,last->r,mid+1,r,x,val);
}
}
char query(node* pos,int l,int r,int x) {
if(l==r) return pos->val;
int mid = (l+r)/2;
if(x<=mid) return query(pos->l,l,mid,x);
return query(pos->r,mid+1,r,x);
}
void Init() {
root[0] = new node;
sz[0] = -1;
build(root[0],0,1000000);
}
void TypeLetter(char L) {
cur++;
root[cur] = new node;
sz[cur] = sz[cur-1] + 1;
upgrade(root[cur],root[cur-1],0,1000000,sz[cur],L);
}
void UndoCommands(int U) {
cur++;
root[cur] = root[cur-U-1];
sz[cur] = sz[cur-U-1];
}
char GetLetter(int P) {
return query(root[cur],0,1000000,P);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
69 ms |
76436 KB |
Output is correct |
2 |
Correct |
73 ms |
76436 KB |
Output is correct |
3 |
Correct |
86 ms |
76436 KB |
Output is correct |
4 |
Correct |
63 ms |
76436 KB |
Output is correct |
5 |
Correct |
73 ms |
76436 KB |
Output is correct |
6 |
Correct |
93 ms |
76436 KB |
Output is correct |
7 |
Correct |
76 ms |
76436 KB |
Output is correct |
8 |
Correct |
83 ms |
76436 KB |
Output is correct |
9 |
Correct |
76 ms |
76436 KB |
Output is correct |
10 |
Correct |
73 ms |
76436 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
83 ms |
76436 KB |
Output is correct |
2 |
Correct |
79 ms |
76436 KB |
Output is correct |
3 |
Correct |
96 ms |
76436 KB |
Output is correct |
4 |
Correct |
96 ms |
76436 KB |
Output is correct |
5 |
Correct |
66 ms |
76436 KB |
Output is correct |
6 |
Correct |
83 ms |
76436 KB |
Output is correct |
7 |
Correct |
59 ms |
76436 KB |
Output is correct |
8 |
Correct |
103 ms |
76436 KB |
Output is correct |
9 |
Correct |
83 ms |
76436 KB |
Output is correct |
10 |
Correct |
86 ms |
76436 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
63 ms |
77228 KB |
Output is correct |
2 |
Correct |
89 ms |
77228 KB |
Output is correct |
3 |
Correct |
79 ms |
77492 KB |
Output is correct |
4 |
Correct |
63 ms |
78284 KB |
Output is correct |
5 |
Correct |
93 ms |
77360 KB |
Output is correct |
6 |
Correct |
96 ms |
78680 KB |
Output is correct |
7 |
Correct |
83 ms |
78680 KB |
Output is correct |
8 |
Correct |
113 ms |
78020 KB |
Output is correct |
9 |
Correct |
123 ms |
78284 KB |
Output is correct |
10 |
Correct |
96 ms |
77228 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Memory limit exceeded |
583 ms |
262144 KB |
Memory limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Memory limit exceeded |
559 ms |
262144 KB |
Memory limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |