| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 377087 | ponytail | 크레이피쉬 글쓰는 기계 (IOI12_scrivener) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "scrivener.h"
#include "bits/stdc++.h"
#define pb push_back
using namespace std;
struct node{
int l,r;
char val;
};
const int MAXN = 23931670;
node a[MAXN];
int sto=-1;
vector<int>version_roots;
vector<int>version_wordlens;
int cnt=0;
int build(int L,int R){
int next_node=++sto;
if(L==R){
a[next_node].val='.';
return next_node;
}
int mid=(L+R)/2;
a[next_node].l=build(L,mid);
a[next_node].r=build(mid+1,R);
return next_node;
}
int update(int node,char yes,int L,int R,int tar){
int next_node=++sto;
if(L==R){
a[next_node].val=yes;
return next_node;
}
int mid=(L+R)/2;
if(tar<=mid){
a[next_node].l=update(a[node].l,yes,L,mid,tar);
a[next_node].r=a[node].r;
}
else{
a[next_node].l=a[node].l;
a[next_node].r=update(a[node].r,yes,mid+1,R,tar);
}
return next_node;
}
char query(int node,int L,int R,int tar){
if(L==R){
return a[node].val;
}
int mid=(L+R)/2;
if(tar<=mid){
return query(a[node].l,L,mid,tar);
}
else{
return query(a[node].r,mid+1,R,tar);
}
}
void Init(){
build(1,1000000);
version_roots.pb(0);
version_wordlens.pb(0);
}
void TypeLetter(char L){
cnt++;
version_roots.pb(sto+1);
version_wordlens.pb(version_wordlens[cnt-1]+1);
update(version_roots[cnt-1],L,1,1000000,version_wordlens[cnt]);
}
void UndoCommands(int U){
cnt++;
version_roots.pb(sto+1);
version_wordlens.pb(version_wordlens[cnt-U-1]);
int next_node=++sto;
a[next_node].l=a[version_roots[cnt-U-1]].l;
a[next_node].r=a[version_roots[cnt-U-1]].r;
}
char GetLetter(int P){
return query(version_roots[cnt],1,1000000,P);
}