| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 749308 | tosivanmak | 크레이피쉬 글쓰는 기계 (IOI12_scrivener) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#ifdef __cplusplus
extern "C" {
#endif
void Init();
void TypeLetter(char L);
void UndoCommands(int U);
char GetLetter(int P);
#ifdef __cplusplus
}
#endif
// TODO: global variables can be declared here
struct info{
char c;
ll lver,rver;
};
struct node{
vector<info>ver;
};
struct SEG{
vector<node>seg;
ll vernochar[1000005];
ll versionofcommand[1000005];
void init(ll n){
seg.resize(4*n+5);
}
void build(ll l, ll r, ll id){
if(l==r){
seg[id].ver.push_back({'-',0,0});
}
else{
ll mid=(l+r)>>1;
build(l,mid,id*2);
build(mid+1,r,id*2+1);
seg[id].ver.push_back({'-',0,0});
}
}
char qry(ll version, ll ql, ll l, ll r, ll id){
if(l==r){
return seg[id].ver[version].c;
}
else{
ll mid=(l+r)>>1;
if(ql<=mid){
return qry(seg[id].ver[version].lver,ql,l,mid,id*2);
}
else{
return qry(seg[id].ver[version].rver,ql,mid+1,r,id*2+1);
}
}
}
void upd(ll version, ll ul, ll l, ll r, char app, ll id){
if(l==r){
seg[id].ver.push_back({app,0,0});
}
else{
ll mid=(l+r)>>1;
if(ul<=mid){
upd(seg[id].ver[version].lver,ul,l,mid,app,id*2);
ll siz=seg[id*2].ver.size()-1;
seg[id].ver.push_back({'-',siz,seg[id].ver[version].rver});
}
else{
upd(seg[id].ver[version].rver,ul,mid+1,r,app,id*2+1);
ll siz=seg[id*2+1].ver.size()-1;
seg[id].ver.push_back({'-',seg[id].ver[version].lver,siz});
}
}
}
};
SEG st;
ll curcom=1;
void Init() {
st.init(1000000);
st.build(1,1000000,1);
st.vernochar[0]=0;
st.versionofcommand[0]=0;
}
void TypeLetter(char L){
// TODO: implementation
ll acccom=curcom-1;
ll lol=st.versionofcommand[acccom];
ll k=st.vernochar[lol];
st.upd(lol,k+1,1,1000000,L,1);
st.vernochar[st.seg[1].ver.size()-1]=k+1;
st.versionofcommand[curcom]=st.seg[1].ver.size()-1;
curcom++;
}
void UndoCommands(int U){
// TODO: implementation
ll acccom=curcom-U-1;
st.versionofcommand[curcom]=st.versionofcommand[acccom];
curcom++;
}
char GetLetter(int P){
// TODO: implementation
ll version=st.versionofcommand[curcom-1];
// cout<<version<<'\n';
P++;
return st.qry(version,P,1,1000000,1);
}