이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 root[1000001];
int nex,version;
struct node{
int child;
int length;
char c;
int anc[21];
node(){
child=-1;
length=0;
c='?';
for (int i=0;i<=20;i++)
anc[i]=-1;
}
};
node arr[1000001];
bool started=false;
void calcAnc(int ind){
arr[ind].anc[0]=arr[ind].child;
for (int i=1;i<=20;i++){
if (arr[ind].anc[i-1]==-1)
arr[ind].anc[i]=-1;
else
arr[ind].anc[i]=arr[arr[ind].anc[i-1]].anc[i-1];
}
}
void Init(){
}
void TypeLetter(char c){
if (!started){
root[0]=0;
arr[0].c=c;
arr[0].length=1;
nex++;
started=true;
return;
}
version++;
root[version]=nex;
arr[nex].length=arr[root[version-1]].length+1;
arr[nex].c=c;
arr[nex].child=root[version-1];
calcAnc(nex);
nex++;
}
void UndoCommands(int x){
version++;
root[version]=nex;
arr[nex].length=arr[root[version-x-1]].length;
arr[nex].c=arr[root[version-x-1]].c;
arr[nex].child=arr[root[version-x-1]].child;
calcAnc(nex);
nex++;
}
char GetLetter(int ind){
ind=arr[root[version]].length-1-ind;
int cur=root[version];
for (int i=20;i>=0;i--){
if (((1<<i)&ind)!=0)
cur=arr[cur].anc[i];
}
return arr[cur].c;
}
# | 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... |