Submission #541617

#	Time	Username	Problem	Language	Result	Execution time	Memory
541617		Deepesson	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	406 ms	143900 KiB

scrivener

#include <bits/stdc++.h>
#define MAX 22000000
const int lim = 1e6+7;
char valor[MAX];
int left[MAX],right[MAX];
int cur=3;

int alocar(void){
    return cur++;
}

void copia(int a,int b){
    left[a]=left[b];
    right[a]=right[b];
    valor[a]=valor[b];
}

char get(int t,int v,int la=0,int ra=lim){
    if(la==ra){
        return valor[v];
    }
    int m = (la+ra)/2;
    if(t<=m){///Left
        return get(t,left[v],la,m);
    }else {///Right
        return get(t,right[v],m+1,ra);
    }
}

void update(int t,char ch,int v,int la=0,int ra=lim){
    if(la==ra){
        valor[v]=ch;
        return;
    }
    int m = (la+ra)/2;
    if(t<=m){///Left
        int prev = left[v];
        left[v]=alocar();
        copia(left[v],prev);
        update(t,ch,left[v],la,m);
    }else {///Right
        int prev = right[v];
        right[v]=alocar();
        copia(right[v],prev);
        update(t,ch,right[v],m+1,ra);
    }
}



std::vector<int> updates;
std::vector<int> size;


void Init() {
    updates.push_back(alocar());
    size.push_back(0);
}

void TypeLetter(char L) {
    int sz = size.back();
    size.push_back(sz+1);
    updates.push_back(alocar());
    copia(updates.back(),updates[updates.size()-2]);
    update(sz,L,updates.back());
}

void UndoCommands(int U) {
    int cord = updates.size()-U-1;
    size.push_back(size[cord]);
    updates.push_back(alocar());
    copia(updates.back(),updates[cord]);
}

char GetLetter(int P) {
    return get(P,updates.back());
}

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