| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 226227 | thtsshz_bgwrswh | 크레이피쉬 글쓰는 기계 (IOI12_scrivener) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optimize("Ofast")
#include "lib1271.h"
#include<stdio.h>
#include<random>
#include<time.h>
#include<algorithm>
using namespace std;
struct Treap{
Treap *l,*r;
int sz;
char c;
Treap(){}
Treap(char _c){
c=_c;
sz=1;
l=r=0;
}
}*treap[1000025];
int cnt;
void pull(Treap *t){
t->sz=(t->l?t->l->sz:0)+(t->r?t->r->sz:0)+1;
}
void copy(Treap *&a,Treap *&b){
a=new Treap;
a->l=b->l;
a->r=b->r;
a->sz=b->sz;
a->c=b->c;
}
Treap* merge(Treap *a,Treap *b){
if(!a||!b)
return a?a:b;
Treap *t;
if(rand()%(a->sz+b->sz)<a->sz){
copy(t,a);
t->r=merge(a->r,b);
pull(t);
}
else{
copy(t,b);
t->l=merge(a,b->l);
pull(t);
}
return t;
}
void split(Treap *t,Treap *&a,Treap *&b,int k){
if(!t){
a=b=0;
return;
}
int l_sz=t->l?t->l->sz:0;
if(l_sz+1<=k){
copy(a,t);
split(t->r,a->r,b,k-l_sz-1);
pull(a);
}
else{
copy(b,t);
split(t->l,a,b->l,k);
pull(b);
}
}
void Init(){
fill(treap,treap+1000025,nullptr);
cnt=0;
}
void TypeLetter(char c){
cnt++;
treap[cnt]=merge(treap[cnt-1],new Treap(c));
}
void UndoCommands(int k){
cnt++;
treap[cnt]=treap[cnt-k-1];
}
char GetLetter(int k){
Treap *left=0,*right=0;
split(treap[cnt],left,treap[cnt],k);
split(treap[cnt],treap[cnt],right,1);
char temp=treap[cnt]->c;
treap[cnt]=merge(merge(left,treap[cnt]),right);
return temp;
}