Submission #567458

#	Time	Username	Problem	Language	Result	Execution time	Memory
567458		shahriarkhan	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	510 ms	246968 KiB

scrivener

#include<bits/stdc++.h>
using namespace std ;

const int MX = 1e6 + 5 ;

int od = 0 ;

string s = "" ;

struct Node
{
    int left = 0 , right = 0 , sum = 0 ;
} emp ;

struct psegtree
{
    int cur = 0 , cnt = 0 , N ;

    vector<Node> T ;

    vector<int> root ;

    void init(int n , int m)
    {
        N = n ;
        T = vector<Node> (20*n + 5 , emp) ;
        root = vector<int> (m + 5 , 0) ;
    }

    int _update(int node , int low , int high , int idx , int val)
    {
        if((idx<low) || (idx>high)) return 0 ;
        if((low==high) && (low==idx))
        {
            ++cur ;
            T[cur].sum = T[node].sum + val ;
            return cur ;
        }
        int mid = (low+high)>>1 , left = T[node].left , right = T[node].right , par = ++cur ;
        if(idx<=mid) T[par].left = _update(left,low,mid,idx,val) , T[par].right = right ;
        else T[par].left = left , T[par].right = _update(right,mid+1,high,idx,val) ;
        T[par].sum = T[T[par].left].sum + T[T[par].right].sum ;
        return par ;
    }

    void add(int idx)
    {
        ++cnt ;
        root[cnt] = _update(root[cnt-1],1,N,idx,1) ;
    }

    void undo(int x)
    {
        ++cnt ;
        root[cnt] = root[cnt-x-1] ;
    }

    int _query(int node , int low , int high , int idx)
    {
        if(low==high) return low ;
        int mid = (low+high)>>1 , left = T[node].left , right = T[node].right ;
        if(T[left].sum>=idx) return _query(left,low,mid,idx) ;
        else return _query(right,mid+1,high,idx-T[left].sum) ;
    }

    int get_val(int idx)
    {
        return _query(root[cnt],1,N,idx) ;
    }
} P ;

void Init()
{
    P.init(MX,MX) ;
}

void TypeLetter(char L)
{
    s += L ;
    P.add(++od) ;
}

void UndoCommands(int U)
{
    P.undo(U) ;
}

char GetLetter(int p)
{
    return s[P.get_val(p+1)-1] ;
}

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