Submission #71762

#	Time	Username	Problem	Language	Result	Execution time	Memory
71762		RezwanArefin01	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	966 ms	151392 KiB

scrivener

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

const int N = 1e6 + 10; 

int t[N][26], p[N][21], idx, d[N];
int tym, node[N], lsb[N], lg[N];  
char c[N]; 

void Init() {
    lg[1] = 0; 
    for(int i = 2; i < N; i++) 
        lg[i] = lg[i >> 1] + 1; 
    for(int i = 1; i < N; i++) 
        lsb[i] = lg[i & -i]; 
}

void TypeLetter(char L) {
    int u = node[tym]; 
    int &v = t[u][L - 'a'];
    if(!v) {
        v = ++idx;
        p[v][0] = u; 
        for(int i = 1; i <= 20 && p[v][i - 1]; i++) 
            p[v][i] = p[p[v][i - 1]][i - 1]; 
    } c[v] = L; 
    node[++tym] = v; 
    d[v] = d[u] + 1; 
}

void UndoCommands(int U) {
    int u = node[tym - U]; 
    node[++tym] = u;
}

char GetLetter(int P) {
    int u = node[tym]; 
    int k = d[u] - P - 1;
    while(k) {
        u = p[u][lsb[k]]; 
        k ^= k & -k;
    } return c[u]; 
}

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