Submission #93543

#	Time	Username	Problem	Language	Result	Execution time	Memory
93543		ansol4328	Crayfish scrivener (IOI12_scrivener)	C++11	74 / 100	1016 ms	217780 KiB

scrivener

#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);
}

Compilation message (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]
     }
     ^

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 22 / 22
• Subtask 4: 0 / 26
• Subtask 5: 40 / 40