| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 379275 | MilosMilutinovic | 크레이피쉬 글쓰는 기계 (IOI12_scrivener) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int N=1000050,M=N*5;
int root[M],ls[M],rs[M],tsz,cnt,sz[N];
char ch[M];
void Set(int p,int&c,int ss,int se,int qi,char L){
c=++tsz;ls[c]=ls[p];rs[c]=rs[p];ch[c]=L;
if(ss==se)return;
int mid=ss+se>>1;
if(qi<=mid)Set(ls[p],ls[c],ss,mid,qi,L);
else Set(rs[p],rs[c],mid+1,se,qi,L);
}
char Get(int c,int ss,int se,int qi){
if(ss==se)return ch[c];
int mid=ss+se>>1;
if(qi<=mid)return Get(ls[c],ss,mid,qi);
else return Get(rs[c],mid+1,se,qi);
}
void Init(){}
void TypeLetter(char L){
cnt++;sz[cnt]=sz[cnt-1];root[cnt]=root[cnt-1];
Set(root[cnt],root[cnt],1,N,sz[cnt],L);
}
void UndoCommands(int x){
cnt++;root[cnt]=root[cnt-x-1];
sz[cnt]=sz[cnt-x-1];
}
char GetLettter(int x){
return Get(root[cnt],1,N,x+1);
}