Submission #917439

#	Time	Username	Problem	Language	Result	Execution time	Memory
917439		jhnah917	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	371 ms	210736 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;
constexpr int LG = 20, SZ = 1 << LG, NODES = SZ * (LG + 3);

int Root[SZ], Len[SZ], L[NODES], R[NODES], V[NODES], C, Pos;
void Init(int node, int s, int e){
    if(s == e) return;
    int m = (s + e) / 2;
    L[node] = ++C; R[node] = ++C;
    Init(L[node], s, m);
    Init(R[node], m+1, e);
}
void Update(int prv, int now, int s, int e, int x, int v){
    if(s == e){ V[now] = v; return; }
    int m = (s + e) / 2;
    if(x <= m){
        L[now] = ++C; R[now] = R[prv];
        Update(L[prv], L[now], s, m, x, v);
    }
    else{
        L[now] = L[prv]; R[now] = ++C;
        Update(R[prv], R[now], m+1, e, x, v);
    }
}
char Get(int node, int s, int e, int x){
    if(s == e) return V[node];
    int m = (s + e) / 2;
    if(x <= m) return Get(L[node], s, m, x);
    else return Get(R[node], m+1, e, x);
}
void Print(int node, int s, int e, int sz){
    if(s >= sz) return;
    if(s == e){ cout << char(V[node]); return; }
    int m = (s + e) / 2;
    Print(L[node], s, m, sz);
    Print(R[node], m+1, e, sz);
}

void Init(){
    Root[0] = ++C;
    Init(Root[0], 0, SZ-1);
}

void TypeLetter(char c){
    Root[++Pos] = ++C; Len[Pos] = Len[Pos-1] + 1;
    Update(Root[Pos-1], Root[Pos], 0, SZ-1, Len[Pos-1], c);
}

void UndoCommands(int k){
    Root[++Pos] = ++C; Len[Pos] = Len[Pos-k-1];
    L[Root[Pos]] = L[Root[Pos-k-1]];
    R[Root[Pos]] = R[Root[Pos-k-1]];
}

char GetLetter(int k){
    return Get(Root[Pos], 0, SZ-1, k);
}

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