#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];
signed ptr[(int)1e6 + 5];
signed ind = 1;
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, node* prev, int ll, char v){
//cout<<"update "<<l<<" "<<u<<" "<<ll<<" "<<v<<"\n";
if(l>=ll && u<=ll){
curr -> val = v;
return curr;
}
if(ll<=mid(l, u)){
curr->left = new node;
if(prev!=nullptr) curr -> left = update(l, mid(l, u), curr->left, prev->left, ll, v);
else curr->left = update(l, mid(l, u), curr->left, nullptr, ll, v);
if(prev!=nullptr) curr -> right = prev -> right;
return curr;
}
if(curr->right == nullptr) curr->right = new node;
if(prev!=nullptr) curr -> right = update(mid(l, u)+1, u, curr->right, prev->right, ll, v);
else curr -> right = update(mid(l, u)+1, u, curr->right, nullptr, ll, v);
if(prev!=nullptr) curr -> left = prev -> left;
return curr;
}
void Init(){
version[0] = new node;
ptr[0] = 0;
}
void TypeLetter(char l){
version[ind] = update(0, 1000000, new node, 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 |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
1280 KB |
Output is correct |
2 |
Correct |
7 ms |
1408 KB |
Output is correct |
3 |
Correct |
7 ms |
1536 KB |
Output is correct |
4 |
Correct |
9 ms |
2304 KB |
Output is correct |
5 |
Correct |
8 ms |
1536 KB |
Output is correct |
6 |
Correct |
10 ms |
2816 KB |
Output is correct |
7 |
Correct |
9 ms |
2688 KB |
Output is correct |
8 |
Correct |
8 ms |
2048 KB |
Output is correct |
9 |
Correct |
8 ms |
2304 KB |
Output is correct |
10 |
Correct |
8 ms |
1408 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
500 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 |
661 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |