oj.uz

Submission #93543

# Submission time Handle Problem Language Result Execution time Memory
93543 2019-01-09T12:42:49 Z ansol4328 Crayfish scrivener (IOI12_scrivener) C++11
74 / 100
 1000 ms 217780 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 207668 KB Output is correct
2 Correct 179 ms 207608 KB Output is correct
3 Correct 179 ms 207740 KB Output is correct
4 Correct 180 ms 207616 KB Output is correct
5 Correct 178 ms 207736 KB Output is correct
6 Correct 181 ms 207632 KB Output is correct
7 Correct 167 ms 207608 KB Output is correct
8 Correct 178 ms 207608 KB Output is correct
9 Correct 154 ms 207608 KB Output is correct
10 Correct 154 ms 207608 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 207736 KB Output is correct
2 Correct 152 ms 207608 KB Output is correct
3 Correct 158 ms 207672 KB Output is correct
4 Correct 173 ms 207808 KB Output is correct
5 Correct 176 ms 207612 KB Output is correct
6 Correct 169 ms 207620 KB Output is correct
7 Correct 177 ms 207580 KB Output is correct
8 Correct 178 ms 207720 KB Output is correct
9 Correct 179 ms 207608 KB Output is correct
10 Correct 179 ms 207584 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 207608 KB Output is correct
2 Correct 178 ms 207628 KB Output is correct
3 Correct 183 ms 207788 KB Output is correct
4 Correct 180 ms 207644 KB Output is correct
5 Correct 181 ms 207860 KB Output is correct
6 Correct 179 ms 207736 KB Output is correct
7 Correct 180 ms 207768 KB Output is correct
8 Correct 179 ms 207736 KB Output is correct
9 Correct 178 ms 207776 KB Output is correct
10 Correct 178 ms 207864 KB Output is correct

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 547 ms 214548 KB Output is correct
2 Correct 539 ms 215212 KB Output is correct
3 Correct 674 ms 216056 KB Output is correct
4 Correct 836 ms 217780 KB Output is correct
5 Correct 572 ms 216072 KB Output is correct
6 Correct 554 ms 215704 KB Output is correct
7 Execution timed out 1016 ms 217132 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 755 ms 215280 KB Output is correct
2 Correct 892 ms 216084 KB Output is correct
3 Correct 718 ms 216368 KB Output is correct
4 Correct 720 ms 217560 KB Output is correct
5 Correct 528 ms 215972 KB Output is correct
6 Correct 609 ms 215928 KB Output is correct
7 Correct 614 ms 216004 KB Output is correct
8 Correct 951 ms 217180 KB Output is correct
9 Correct 976 ms 216664 KB Output is correct
10 Correct 508 ms 215660 KB Output is correct