#include <bits/stdc++.h>
using namespace std;
#define N (int)1e6+1
#define maxp 22
struct ano{
char c;
int sons[26];
};
ano trie[N+1];
int curr=0;
int t=1;
int lift[N+1][maxp];
int googleChrome[N+1];
int d[N+1];
int cnt=1;
void Init() {
}
void TypeLetter(char c) {
int next=trie[curr].sons[c-'a'];
if(next==0){
trie[curr].sons[c-'a']=cnt;
d[cnt]=d[curr]+1;
trie[cnt].c=c;
lift[cnt][0]=curr;
curr=cnt;
int i;
for(i=1;i<maxp;i++)
lift[curr][i]=lift[lift[curr][i-1]][i-1];
cnt++;
}
else
curr=next;
googleChrome[t++]=curr;
// cout<<t<<" "<<curr<<" "<<trie[curr].c<<endl;
}
void UndoCommands(int n) {
curr=googleChrome[t-n-1];
// int i;
// for(i=1;i<t;i++)
// cout<<googleChrome[i]<<" ";
// cout<<endl;
googleChrome[t++]=curr;
//cout<<t<<" "<<curr<<" "<<trie[curr].c<<endl;
}
char GetLetter(int x) {
//cout<<d[curr]<<" "<<curr<<endl;
int k=d[curr]-x-1;
int i;
int ans=curr;
for(i=maxp-1;i>=0;i--)
if(k>=(1<<i)){
k-=(1<<i);
ans=lift[ans][i];
}
// cout<<ans<<endl;
return trie[ans].c;
}
# |
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 |
4 ms |
384 KB |
Output is correct |
5 |
Correct |
4 ms |
384 KB |
Output is correct |
6 |
Correct |
4 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
512 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 |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
384 KB |
Output is correct |
4 |
Correct |
4 ms |
384 KB |
Output is correct |
5 |
Correct |
4 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 |
640 KB |
Output is correct |
2 |
Correct |
6 ms |
640 KB |
Output is correct |
3 |
Correct |
6 ms |
640 KB |
Output is correct |
4 |
Correct |
6 ms |
896 KB |
Output is correct |
5 |
Correct |
6 ms |
768 KB |
Output is correct |
6 |
Correct |
6 ms |
1152 KB |
Output is correct |
7 |
Correct |
6 ms |
1152 KB |
Output is correct |
8 |
Correct |
6 ms |
896 KB |
Output is correct |
9 |
Correct |
6 ms |
896 KB |
Output is correct |
10 |
Correct |
6 ms |
640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
438 ms |
116008 KB |
Output is correct |
2 |
Correct |
480 ms |
131248 KB |
Output is correct |
3 |
Correct |
421 ms |
128480 KB |
Output is correct |
4 |
Correct |
412 ms |
98680 KB |
Output is correct |
5 |
Correct |
455 ms |
111864 KB |
Output is correct |
6 |
Correct |
377 ms |
141632 KB |
Output is correct |
7 |
Correct |
398 ms |
70984 KB |
Output is correct |
8 |
Correct |
388 ms |
106488 KB |
Output is correct |
9 |
Correct |
485 ms |
145632 KB |
Output is correct |
10 |
Correct |
283 ms |
106732 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
546 ms |
98116 KB |
Output is correct |
2 |
Correct |
629 ms |
91256 KB |
Output is correct |
3 |
Correct |
404 ms |
98300 KB |
Output is correct |
4 |
Correct |
413 ms |
72528 KB |
Output is correct |
5 |
Correct |
370 ms |
108408 KB |
Output is correct |
6 |
Correct |
398 ms |
101168 KB |
Output is correct |
7 |
Correct |
397 ms |
108152 KB |
Output is correct |
8 |
Correct |
486 ms |
53496 KB |
Output is correct |
9 |
Correct |
578 ms |
94568 KB |
Output is correct |
10 |
Correct |
308 ms |
105896 KB |
Output is correct |