Submission #194320

#	Time	Username	Problem	Language	Result	Execution time	Memory
194320		oscarsierra12	Crayfish scrivener (IOI12_scrivener)	C++14	0 / 100	1107 ms	231596 KiB

scrivener

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

const int N = 1e6+2 ;
int L[ 20*N ], R[ 20*N ], lazy [ 20*N ], sum [ 20*N ] ;
int lst[N], nec[N], q, last = 0, cur = 0;
char let[N] ;
int nodeG = 0;
int visit[N] ;
string ans ;

struct info {
    int l, r, nod ;
};

info fll ( int li, int ri, int node ) {
    info x = {li,ri,node} ;
    return x ;
}

int build ( info i ) {
    if ( i.l == i.r )
        return i.nod ;
    info x = fll ( i.l, (i.l+i.r)/2, ++nodeG ) ;
    L[i.nod] = build ( x ) ;
    x = fll ( (i.l+i.r)/2+1, i.r, ++nodeG ) ;
    R[i.nod] = build ( x ) ;
    return i.nod ;
}

void propagate ( info i ) {
    if ( lazy[i.nod] == -1 ) return ;
    if ( L[i.nod] ) lazy[L[i.nod]] = lazy[i.nod] ;
    if ( R[i.nod] ) lazy[R[i.nod]] = lazy[i.nod] ;
    sum[i.nod] = lazy[i.nod]*(i.r-i.l+1) ;
    lazy[i.nod] = -1 ;
}

void update ( info i, int a, int b, int val ) {
    if ( a > b ) return ;
    propagate ( i ) ;
    int mid = (i.l+i.r)/2 ;
    if ( i.l == a && i.r == b ) {
        lazy[i.nod] = val ;
        propagate ( i ) ;
        return ;
    }
    info x = fll(i.l,mid,L[i.nod]) ;
    info x2 = fll(mid+1, i.r, R[i.nod]) ;
    if ( b <= mid ) update ( x, a, b, val ) ;
    else if ( a > mid ) update ( x2, a, b, val ) ;
    else {
        update (x, a, mid, val) ;
        update (x2, mid+1, b, val );
    }
    sum[i.nod] = sum[L[i.nod]] + sum[R[i.nod]] ;
}

int query ( info i, int a, int b ) {
    if ( a > b ) return 0 ;
    propagate(i) ;
    if ( i.l == a && i.r == b ) return sum[i.nod] ;
    int mid = (i.l+i.r)/2 ;
    info x = fll(i.l,mid,L[i.nod]) ;
    info x2 = fll(mid+1, i.r, R[i.nod]) ;
    if ( b <= mid ) return query ( x, a, b ) ;
    if ( a > mid ) return query ( x2, a, b ) ;
    return query (x, a, mid) + query (x2, mid+1, b );
}

info fr ;

void Init() {
    fr = fll(1,N-1,0) ;
    memset ( lazy, -1, sizeof lazy ) ;
    build ( fr ) ;
    q = 0;
    visit[0] = 1 ;
}

void TypeLetter(char L) {
    ++q ;
    lst[q] = lst[q-1] ;
    update ( fr, q, q, 1 ) ;
    let[q] = L ;
}

void UndoCommands(int U) {
    ++q ;
    lst[q] = q ;
    nec[q] = U ;
    last = q ;
}

char GetLetter(int P) {
    if ( last == 0 )
        for ( int i = q; i ; --i ) ans.push_back (let[i]) ;
    while ( !visit[last] ) {
        int pos = lst[last] - nec[last] - 1 ;
        for ( int i = pos ; i > lst[pos] ; --i ) ans.push_back(let[i]);
        visit[last] = 1 ;
        last = lst [ pos ] ;
    }
    if ( !cur ) reverse(ans.begin(), ans.end()), cur= 1 ;
//    int lw = 1, hg = q ;
//    P++ ;
//    while ( lw < hg ) {
//        int mid = (lw+hg+1) / 2 ;
//        int letters = query ( fr, 1, mid ) ;
//        if ( letters < P ) lw = mid ;
//        else if ( letters > P ) hg = mid-1 ;
//        else {
//            if ( query(fr, mid,mid) ) lw = mid ;
//            else hg = mid-1 ;
//        }
//    }
    return ans[P] ;
}

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