이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<vector>
using namespace std;
struct PST
{
vector<char> tree;
vector<int> left, right, root;
int height, t, base;
PST(int a, int b, int rn)
{
base=height=1, t=0;
while(base<a) height++, base=base<<1;
int tmp=base*2+2+height*b+5;
tree.resize(tmp);
left.resize(tmp);
right.resize(tmp);
root.resize(rn+2);
root[0]=setup(1,base);
}
int setup(int ns, int nf)
{
int k=t++;
tree[k]=0;
if(ns<nf)
{
int mid=(ns+nf)>>1;
left[k]=setup(ns,mid);
right[k]=setup(mid+1,nf);
}
return k;
}
void update_Kth_tree(int bef, int k, int idx, char val)
{
root[k]=make(root[bef],idx,val);
}
int make(int bef, int idx, char val, int ns=1, int nf=-1)
{
if(nf==-1) nf=base;
if(idx<ns || nf<idx) return bef;
int k=t++;
if(ns==nf) tree[k]=val;
else
{
int mid=(ns+nf)>>1;
left[k]=make(left[bef],idx,val,ns,mid);
right[k]=make(right[bef],idx,val,mid+1,nf);
tree[k]=val;
}
return k;
}
char get_char(int num, int idx, int ns=1, int nf=-1)
{
if(nf==-1) nf=base;
if(ns==nf) return tree[num];
int mid=(ns+nf)>>1;
if(ns<=idx && idx<=mid)
return get_char(left[num],idx,ns,mid);
if(mid+1<=idx && idx<=nf)
return get_char(right[num],idx,mid+1,nf);
}
};
int len[1000002], cnt;
PST T(1000002,1000002,1000002);
void Init() {}
void TypeLetter(char L)
{
cnt++;
len[cnt]=len[cnt-1]+1;
T.update_Kth_tree(cnt-1,cnt,len[cnt],L);
}
void UndoCommands(int U)
{
cnt++;
len[cnt]=len[cnt-U-1];
T.update_Kth_tree(cnt-U-1,cnt,len[cnt]+1,0);
}
char GetLetter(int P)
{
return T.get_char(T.root[cnt],P+1);
}
컴파일 시 표준 에러 (stderr) 메시지
scrivener.cpp: In member function 'char PST::get_char(int, int, int, int)':
scrivener.cpp:61:5: warning: control reaches end of non-void function [-Wreturn-type]
}
^
# | 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... |