#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,N) for(ll i = 0; i < N; i++)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
vector<int> cmd = {0}; // cmd[i] -> idx of cur node after ith command (1-indexed)
vector<int> len = {0}; // len[i] -> len of cur string after ith command (1-indexed)
vector<char> node; // node value
vector<vector<int>> par(2e6, vector<int>(20)); // node parent (binary jumping)
int n = 0; // nodes created
void Init() {}
void TypeLetter(char ch) {
len.push_back(len[cmd[cmd.size()-1]] + 1);
par[n][0] = cmd[cmd.size()-1];
cmd.push_back(n);
node.push_back(ch);
for(int j = 1; j < 20; j++) par[n][j] = par[par[n][j-1]][j-1];
n++;
}
void UndoCommands(int k) {
cmd.push_back(cmd[cmd.size()-1-k]);
}
char GetLetter(int k) {
k -= len[cmd[cmd.size()-1] + 1];
int j = 19;
int bru = cmd[cmd.size()-1];
while(j > -1) {
if (pow(2, j) <= k) {
bru = par[bru][j];
k -= pow(2, j);
}
j--;
}
return node[bru];
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |