#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <iomanip>
#include <deque>
#include <cassert>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <chrono>
#include <ctime>
#include <random>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#include <iterator>
#include <climits>
//#include "scrivener.h"
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001
#define MOD 1000000007
int nex;
int length[1000001];
char c[1000001];
vector<int> anc[1000001];
bool started=false;
int LOG[1000001];
void calcAnc(int ind){
for (int i=1;i<=LOG[length[ind]]+1;i++){
if (anc[ind][i-1]==-1 || i-1>=(int)anc[anc[ind][i-1]].size())
anc[ind].push_back(-1);
else
anc[ind].push_back(anc[anc[ind][i-1]][i-1]);
}
}
void Init(){
anc[0].push_back(-1);
for (int i=0;i<20;i++)
LOG[1<<i]=i;
for (int i=1;i<=1000000;i++)
if (LOG[i]==0)
LOG[i]=LOG[i-1];
}
void TypeLetter(char ch){
if (!started){
c[0]=ch;
length[0]=1;
nex++;
started=true;
return;
}
length[nex]=length[nex-1]+1;
c[nex]=ch;
anc[nex].push_back(nex-1);
calcAnc(nex);
nex++;
}
void UndoCommands(int x){
length[nex]=length[nex-x-1];
c[nex]=c[nex-x-1];
anc[nex].push_back(anc[nex-x-1][0]);
calcAnc(nex);
nex++;
}
char GetLetter(int ind){
ind=length[nex-1]-1-ind;
int cur=nex-1;
for (int i=(int)anc[cur].size()-1;i>=0;i--){
if (((1<<i)&ind)!=0)
cur=anc[cur][i];
}
return c[cur];
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
32 ms |
27768 KB |
Output is correct |
2 |
Correct |
32 ms |
27768 KB |
Output is correct |
3 |
Correct |
32 ms |
27768 KB |
Output is correct |
4 |
Correct |
37 ms |
27768 KB |
Output is correct |
5 |
Correct |
38 ms |
27896 KB |
Output is correct |
6 |
Correct |
38 ms |
27768 KB |
Output is correct |
7 |
Correct |
38 ms |
27820 KB |
Output is correct |
8 |
Correct |
38 ms |
27768 KB |
Output is correct |
9 |
Correct |
41 ms |
27768 KB |
Output is correct |
10 |
Correct |
37 ms |
27768 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
37 ms |
27676 KB |
Output is correct |
2 |
Correct |
34 ms |
27756 KB |
Output is correct |
3 |
Correct |
32 ms |
27768 KB |
Output is correct |
4 |
Correct |
34 ms |
27768 KB |
Output is correct |
5 |
Correct |
32 ms |
27768 KB |
Output is correct |
6 |
Correct |
32 ms |
27768 KB |
Output is correct |
7 |
Correct |
19 ms |
27768 KB |
Output is correct |
8 |
Correct |
31 ms |
27676 KB |
Output is correct |
9 |
Correct |
32 ms |
27768 KB |
Output is correct |
10 |
Correct |
32 ms |
27700 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
33 ms |
27896 KB |
Output is correct |
2 |
Correct |
34 ms |
27996 KB |
Output is correct |
3 |
Correct |
35 ms |
28152 KB |
Output is correct |
4 |
Correct |
33 ms |
28000 KB |
Output is correct |
5 |
Correct |
34 ms |
28024 KB |
Output is correct |
6 |
Correct |
35 ms |
28280 KB |
Output is correct |
7 |
Correct |
34 ms |
27924 KB |
Output is correct |
8 |
Correct |
36 ms |
28152 KB |
Output is correct |
9 |
Correct |
35 ms |
28152 KB |
Output is correct |
10 |
Correct |
35 ms |
28152 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1049 ms |
133296 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1048 ms |
109896 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |