#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define F first
#define S second
typedef vector<ll> vi;
typedef pair<ll, ll> ii;
typedef map<ll,ll> mii;
#define L 20
#define INF 1000001
int d[INF];
struct tri{
char lastlet;
struct tri *children[27];
};
struct tri *getNode(){
tri *n = new tri;
for(int i=0;i<26;i++)
n->children[i] = NULL;
return n;
}
int upp[INF][L+1] = {};
int anc(int n, int k){
int cnt=0;
if(k>d[n]) return 0;
while(k>0){
if(k%2) n = upp[n][cnt];
cnt++;
k/=2;
}
return n;
}
void pre(int n){
//cout<<n<<endl;
for(int i=1;i<L;i++){
upp[n][i] = anc(upp[n][0], (1ll<<i)-1);
//cout<<i<<" "<<upp[n][i]<<endl;
}
//cout<<"---\n";
}
tri *trie;
void pr(int ind=0, tri* z=trie, tri* node=NULL){
for(int i=0;i<26;i++){
if(z->children[i]!=NULL){
cout<<"\\";
for(int i=0;i<ind;i++) cout<<' ';
if(z->children[i]!=node) cout<<(char)(i+'a')<<endl;
else cout<<(char)(i+'A')<<endl;
pr(ind+1, z->children[i], node);
}
}
}
vector<pair<tri*, int> > history;
void Init(){
ios::sync_with_stdio(false);
cin.tie(0);
trie = getNode();
for(int i=0;i<INF;i++){
for(int j=0;j<=L;j++){
upp[i][j] = INF+10;
}
}
history.push_back(make_pair(trie, 0));
}
void TypeLetter(char a){
history[history.size()-1].F->children[a-'a'] = getNode();
upp[history.size()][0] = history[history.size()-1].S;
//cout<<"| "<<history.size()<<endl;
d[history.size()] = d[history[history.size()-1].S]+1;
history.push_back(make_pair(history[history.size()-1].F->children[a-'a'], history.size()));
history[history.size()-1].F->lastlet = a;
//pr(0, trie, history[history.size()-1].F);
pre(history[history.size()-1].S);
}
void UndoCommands(int a){
d[history.size()] = d[history[history.size()-1-a].S];
history.push_back(history[history.size()-a-1]);
}
char GetLetter(int pos){
return history[anc(history[history.size()-1].S, d[history[history.size()-1].S] - pos-1)].F->lastlet;
}
/*
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
trie = getNode();
int n;
cin>>n;
for(int i=0;i<INF;i++){
for(int j=0;j<=L;j++){
upp[i][j] = INF+10;
}
}
vector<pair<tri*, int> > history;
history.push_back(make_pair(trie, 0));
while(n--){
char c;
cin>>c;
//cout<<c<<" ";
if(c=='T'){
char a;
cin>>a;
//trie[TIME]->children[a-'a'] = getNode();
history[history.size()-1].F->children[a-'a'] = getNode();
upp[history.size()][0] = history[history.size()-1].S;
//cout<<"| "<<history.size()<<endl;
d[history.size()] = d[history[history.size()-1].S]+1;
history.push_back(make_pair(history[history.size()-1].F->children[a-'a'], history.size()));
history[history.size()-1].F->lastlet = a;
//pr(0, trie, history[history.size()-1].F);
pre(history[history.size()-1].S);
//cout<<"---------\n";
}
if(c=='U'){
int a;
cin>>a;
//cout<<" "<<history.size()<<endl;
d[history.size()] = d[history[history.size()-1-a].S];
history.push_back(history[history.size()-a-1]);
//pr(0, trie, history[history.size()-1].F);
//cout<<"---------\n";
}
if(c=='P'){
int pos;
cin>>pos;
/
string s = "";
int q = history[history.size()-1].S;
while(q!=0){
s+=history[q].F->lastlet;
q = upp[q][0];
}
cout<<s[s.size()-pos-1]<<endl;
/
//pre(history[history.size()-1].S);
cout<<history[anc(history[history.size()-1].S, d[history[history.size()-1].S] - pos-1)].F->lastlet<<"\n";
}
}
//pr();
}
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
45 ms |
82552 KB |
Output is correct |
2 |
Correct |
47 ms |
82584 KB |
Output is correct |
3 |
Correct |
46 ms |
82552 KB |
Output is correct |
4 |
Correct |
45 ms |
82552 KB |
Output is correct |
5 |
Correct |
46 ms |
82552 KB |
Output is correct |
6 |
Correct |
46 ms |
82552 KB |
Output is correct |
7 |
Correct |
47 ms |
82552 KB |
Output is correct |
8 |
Correct |
47 ms |
82552 KB |
Output is correct |
9 |
Correct |
46 ms |
82552 KB |
Output is correct |
10 |
Correct |
46 ms |
82552 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
45 ms |
82552 KB |
Output is correct |
2 |
Correct |
46 ms |
82552 KB |
Output is correct |
3 |
Correct |
46 ms |
82552 KB |
Output is correct |
4 |
Correct |
46 ms |
82552 KB |
Output is correct |
5 |
Correct |
45 ms |
82552 KB |
Output is correct |
6 |
Correct |
49 ms |
82552 KB |
Output is correct |
7 |
Correct |
49 ms |
82552 KB |
Output is correct |
8 |
Correct |
47 ms |
82552 KB |
Output is correct |
9 |
Correct |
46 ms |
82552 KB |
Output is correct |
10 |
Correct |
46 ms |
82552 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
46 ms |
82936 KB |
Output is correct |
2 |
Correct |
49 ms |
82940 KB |
Output is correct |
3 |
Correct |
47 ms |
83064 KB |
Output is correct |
4 |
Correct |
47 ms |
83320 KB |
Output is correct |
5 |
Correct |
55 ms |
83036 KB |
Output is correct |
6 |
Correct |
48 ms |
83448 KB |
Output is correct |
7 |
Correct |
47 ms |
83448 KB |
Output is correct |
8 |
Correct |
47 ms |
83320 KB |
Output is correct |
9 |
Correct |
48 ms |
83380 KB |
Output is correct |
10 |
Correct |
48 ms |
82936 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
630 ms |
236480 KB |
Output is correct |
2 |
Correct |
682 ms |
253380 KB |
Output is correct |
3 |
Correct |
631 ms |
250820 KB |
Output is correct |
4 |
Correct |
642 ms |
220352 KB |
Output is correct |
5 |
Correct |
659 ms |
229440 KB |
Output is correct |
6 |
Runtime error |
596 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
675 ms |
210392 KB |
Output is correct |
2 |
Correct |
728 ms |
195928 KB |
Output is correct |
3 |
Correct |
575 ms |
207288 KB |
Output is correct |
4 |
Correct |
565 ms |
174784 KB |
Output is correct |
5 |
Correct |
576 ms |
220224 KB |
Output is correct |
6 |
Correct |
577 ms |
213032 KB |
Output is correct |
7 |
Correct |
595 ms |
221244 KB |
Output is correct |
8 |
Correct |
698 ms |
150092 KB |
Output is correct |
9 |
Correct |
758 ms |
199368 KB |
Output is correct |
10 |
Correct |
437 ms |
218816 KB |
Output is correct |