Submission #806398

#	Time	Username	Problem	Language	Result	Execution time	Memory
806398		QwertyPi	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	530 ms	198116 KiB

scrivener

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e6 + 11;
struct Node{
    char c;
    int nxt[26] = {};
    int lift[20] = {};
    int pos = -1;
} t[MAXN];

int trie_id = 0;

int extend(int v, char c){
    if(!t[v].nxt[c - 'a']) t[v].nxt[c - 'a'] = trie_id++;
    int u = t[v].nxt[c - 'a'];
    t[u].c = c; t[u].lift[0] = v; t[u].pos = t[v].pos + 1;
    for(int j = 1; j < 20; j++) t[u].lift[j] = t[t[u].lift[j - 1]].lift[j - 1];
    return u;
}

int root[MAXN], id = 0;
void Init() {
    root[0] = 0; trie_id++;
}

void TypeLetter(char L) {
    ++id; root[id] = extend(root[id - 1], L);
}

void UndoCommands(int U) {
    ++id; root[id] = root[id - U - 1];
}

char GetLetter(int P) {
    int v = root[id];
    for(int j = 19; j >= 0; j--){
        if(t[v].pos - P >= (1 << j)){
            v = t[v].lift[j];
        }
    }
    return t[v].c;
}

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