#include <bits/stdc++.h>
using namespace std;
struct node{
int p;
int len;
char c;
};
node arr[1000005];
int crnt = 0, idx = 0;
int tbl[20][1000005];
void Init(){
arr[0] = {-1, 0, ' '};
}
void add(int idx){
for(int d = 1; d<20; d++){
tbl[d][idx] = tbl[d-1][tbl[d-1][idx]];
}
}
void TypeLetter(char c){
arr[++idx] = {crnt, arr[crnt].len+1, c};
tbl[0][idx] = crnt;
add(idx);
crnt = idx;
}
void UndoCommands(int u){
int k = crnt;
while(u--){
crnt = arr[crnt].p;
}
arr[++idx] = arr[crnt];
arr[idx].p = k;
add(idx);
crnt = idx;
}
char GetLetter(int p){
int t = crnt;
p++;
for(int d = 19; d>=0; d--){
if(arr[tbl[d][t]].len >= p){
t = tbl[d][t];
}
}
return arr[t].c;
}
/*
int main(){
Init();
TypeLetter('a');
TypeLetter('b');
cout << GetLetter(1) << endl;
TypeLetter('d');
UndoCommands(2);
UndoCommands(1);
cout << GetLetter(2) << endl;
TypeLetter('e');
UndoCommands(1);
UndoCommands(5);
TypeLetter('c');
cout << GetLetter(2) << endl;
UndoCommands(2);
cout << GetLetter(2) << endl;
}
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
504 KB |
Output is correct |
2 |
Correct |
2 ms |
504 KB |
Output is correct |
3 |
Correct |
2 ms |
504 KB |
Output is correct |
4 |
Correct |
2 ms |
504 KB |
Output is correct |
5 |
Correct |
0 ms |
504 KB |
Output is correct |
6 |
Correct |
7 ms |
504 KB |
Output is correct |
7 |
Correct |
2 ms |
504 KB |
Output is correct |
8 |
Correct |
2 ms |
504 KB |
Output is correct |
9 |
Correct |
3 ms |
504 KB |
Output is correct |
10 |
Correct |
2 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
504 KB |
Output is correct |
2 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
696 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1042 ms |
19628 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1036 ms |
17504 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |