#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
#define pb push_back
#define f first
#define s second
const int MAXN = 1e6 + 1e3;
const int LOGN = 21;
char lets[MAXN];
int L[MAXN], nLetI[MAXN], jmp[MAXN][LOGN];
void Init() {
memset(lets, 0, sizeof(lets));
memset(L, 0, sizeof(L));
memset(nLetI, 0, sizeof(nLetI));
memset(jmp, 0, sizeof(jmp));
}
int cI = 1;
void computeJump(int i) {
for (int log = 1; log < LOGN; log++) {
jmp[i][log] = jmp[jmp[i][log - 1]][log - 1];
}
}
void TypeLetter(char cLet) {
lets[cI] = cLet;
L[cI] = L[cI - 1] + 1;
if (lets[cI - 1] == 0) {
nLetI[cI] = nLetI[cI - 1];
} else {
nLetI[cI] = cI - 1;
}
jmp[cI][0] = nLetI[cI];
computeJump(cI);
cI++;
}
void UndoCommands(int U) {
L[cI] = L[cI - U - 1];
if (lets[cI - U - 1] == 0) {
nLetI[cI] = nLetI[cI - U - 1];
} else {
nLetI[cI] = cI - U - 1;
}
jmp[cI][0] = nLetI[cI];
computeJump(cI);
cI++;
}
char GetLetter(int P) {
int nJ = L[cI - 1] - P - 1;
int i = cI - 1;
if (lets[i] == 0) {
i = nLetI[i];
}
for (int log = LOGN - 1; log >= 0; log--) {
int jmps = 1 << log;
if (jmps <= nJ) {
i = jmp[i][log];
nJ -= jmps;
}
}
return lets[i];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
78 ms |
91384 KB |
Output is correct |
2 |
Correct |
77 ms |
91512 KB |
Output is correct |
3 |
Correct |
76 ms |
91384 KB |
Output is correct |
4 |
Correct |
76 ms |
91384 KB |
Output is correct |
5 |
Correct |
76 ms |
91512 KB |
Output is correct |
6 |
Correct |
76 ms |
91384 KB |
Output is correct |
7 |
Correct |
76 ms |
91512 KB |
Output is correct |
8 |
Correct |
76 ms |
91356 KB |
Output is correct |
9 |
Correct |
76 ms |
91640 KB |
Output is correct |
10 |
Correct |
76 ms |
91384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
76 ms |
91504 KB |
Output is correct |
2 |
Correct |
76 ms |
91368 KB |
Output is correct |
3 |
Correct |
77 ms |
91512 KB |
Output is correct |
4 |
Correct |
77 ms |
91384 KB |
Output is correct |
5 |
Correct |
76 ms |
91384 KB |
Output is correct |
6 |
Correct |
75 ms |
91384 KB |
Output is correct |
7 |
Correct |
77 ms |
91384 KB |
Output is correct |
8 |
Correct |
76 ms |
91464 KB |
Output is correct |
9 |
Correct |
78 ms |
91384 KB |
Output is correct |
10 |
Correct |
77 ms |
91384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
77 ms |
91384 KB |
Output is correct |
2 |
Correct |
78 ms |
91452 KB |
Output is correct |
3 |
Correct |
78 ms |
91384 KB |
Output is correct |
4 |
Correct |
88 ms |
91444 KB |
Output is correct |
5 |
Correct |
77 ms |
91384 KB |
Output is correct |
6 |
Correct |
79 ms |
91444 KB |
Output is correct |
7 |
Correct |
90 ms |
91512 KB |
Output is correct |
8 |
Correct |
90 ms |
91384 KB |
Output is correct |
9 |
Correct |
99 ms |
91384 KB |
Output is correct |
10 |
Correct |
89 ms |
91512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
545 ms |
95360 KB |
Output is correct |
2 |
Correct |
657 ms |
95752 KB |
Output is correct |
3 |
Correct |
461 ms |
96632 KB |
Output is correct |
4 |
Correct |
508 ms |
98040 KB |
Output is correct |
5 |
Correct |
552 ms |
96832 KB |
Output is correct |
6 |
Correct |
437 ms |
95864 KB |
Output is correct |
7 |
Execution timed out |
1006 ms |
97848 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
670 ms |
96508 KB |
Output is correct |
2 |
Correct |
679 ms |
97548 KB |
Output is correct |
3 |
Correct |
457 ms |
97492 KB |
Output is correct |
4 |
Correct |
487 ms |
98936 KB |
Output is correct |
5 |
Correct |
478 ms |
96460 KB |
Output is correct |
6 |
Correct |
498 ms |
96248 KB |
Output is correct |
7 |
Correct |
483 ms |
96504 KB |
Output is correct |
8 |
Execution timed out |
1008 ms |
98156 KB |
Time limit exceeded |
9 |
Halted |
0 ms |
0 KB |
- |