#include <bits/stdc++.h>
#define int long long
#define INF 1000000000000000
#define lchild(i) (i*2 + 1)
#define rchild(i) (i*2 + 2)
#define mid(l, u) ((l+u)/2)
#define x(p) p.first
#define y(p) p.second
#define MOD 998244353
using namespace std;
struct node{
node* left;
node* right;
char val;
};
node* version[(int)1e6 + 5];
int ptr[(int)1e6 + 5];
int ind = 1;
char build(int l, int u, int i, node* curr){
if(l==u){
return curr->val = 'a';
}
return curr->val = max(build(l, mid(l, u), lchild(i), curr->left = new node), build(mid(l, u)+1, u, rchild(i), curr->right = new node));
}
char query(int l, int u, int ll, node* curr){
if(l>=ll && u<=ll) return curr->val;
if(ll<=mid(l, u)){
return query(l, mid(l, u), ll, curr->left);
}
return query(mid(l, u)+1, u, ll, curr->right);
}
node* update(int l, int u, node* curr, int ll, char v){
node* temp = new node;
if(l>=ll && u<=ll){
temp -> val = v;
return temp;
}
if(ll<=mid(l, u)){
temp -> left = update(l, mid(l, u), curr->left, ll, v);
temp -> right = curr -> right;
return temp;
}
temp -> right = update(mid(l, u)+1, u, curr->right, ll, v);
temp -> left = curr -> left;
return temp;
}
void Init(){
version[0] = new node;
build(0, 1000000, 0, version[0]);
ptr[0] = 0;
}
void TypeLetter(char l){
version[ind] = update(0, 1000000, version[ind - 1], ptr[ind-1], l);
ptr[ind] = ptr[ind-1] + 1;
ind++;
}
void UndoCommands(signed u){
version[ind] = version[ind-1-u];
ptr[ind] = ptr[ind - 1 - u];
ind++;
}
char GetLetter(signed p){
return query(0, 1000000, p, version[ind - 1]);
}
/*signed main(){
Init();
int q;
cin>>q;
while(q--){
int type;
cin>>type;
if(type==1){
char l;
cin>>l;
TypeLetter(l);
}
else if(type==2){
int u;
cin>>u;
UndoCommands(u);
}
else{
int pos;
cin>>pos;
cout<<GetLetter(pos)<<endl;
}
}
}*/
/*
1 a
1 b
3 1
1 d
2 2
2 1
3 2
1 e
2 1
2 5
1 c
3 2
2 2
3 2
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
88 ms |
62968 KB |
Output is correct |
2 |
Correct |
86 ms |
62972 KB |
Output is correct |
3 |
Correct |
85 ms |
62968 KB |
Output is correct |
4 |
Correct |
83 ms |
62968 KB |
Output is correct |
5 |
Correct |
90 ms |
62968 KB |
Output is correct |
6 |
Correct |
85 ms |
62968 KB |
Output is correct |
7 |
Correct |
85 ms |
62968 KB |
Output is correct |
8 |
Correct |
85 ms |
62968 KB |
Output is correct |
9 |
Correct |
83 ms |
62968 KB |
Output is correct |
10 |
Correct |
90 ms |
62968 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
91 ms |
62912 KB |
Output is correct |
2 |
Correct |
83 ms |
63096 KB |
Output is correct |
3 |
Correct |
93 ms |
62968 KB |
Output is correct |
4 |
Correct |
83 ms |
62968 KB |
Output is correct |
5 |
Correct |
86 ms |
63096 KB |
Output is correct |
6 |
Correct |
89 ms |
62956 KB |
Output is correct |
7 |
Correct |
93 ms |
63096 KB |
Output is correct |
8 |
Correct |
84 ms |
62968 KB |
Output is correct |
9 |
Correct |
87 ms |
62968 KB |
Output is correct |
10 |
Correct |
85 ms |
62968 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
86 ms |
63908 KB |
Output is correct |
2 |
Correct |
94 ms |
63992 KB |
Output is correct |
3 |
Correct |
87 ms |
64120 KB |
Output is correct |
4 |
Correct |
89 ms |
64888 KB |
Output is correct |
5 |
Correct |
85 ms |
64232 KB |
Output is correct |
6 |
Correct |
91 ms |
65376 KB |
Output is correct |
7 |
Correct |
91 ms |
65332 KB |
Output is correct |
8 |
Correct |
90 ms |
64760 KB |
Output is correct |
9 |
Correct |
91 ms |
64888 KB |
Output is correct |
10 |
Correct |
87 ms |
63920 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
424 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
551 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |