Submission #27742

#	Time	Username	Problem	Language	Result	Execution time	Memory
27742		zoomswk	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	596 ms	208208 KiB

scrivener

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

char last;

const int N = 1e6;

char t[23*N];
int L[23*N], R[23*N];
int root[N+5];
int nodecnt=2;
int cur_t = 1;

void build(int node, int l, int r){
    if(l == r) return;
    L[node] = nodecnt++;
    R[node] = nodecnt++;
    int mid = (l+r)>>1;
    build(L[node], l, mid);
    build(R[node], mid+1, r);
    return;
}

void upd(int prev_node, int node, int l, int r, char ch){
    if(l == r){
        t[node] = ch;
        return;
    }
    L[node] = L[prev_node], R[node] = R[prev_node];
    int mid = (l+r)>>1;
    if(t[L[node]]){
        R[node] = nodecnt++;
        upd(R[prev_node], R[node], mid+1, r, ch);
    } else{
        L[node] = nodecnt++;
        upd(L[prev_node], L[node], l, mid, ch);
    }
    t[node] = t[R[node]];
    return;
}

char qr(int node, int l, int r, int targ){
    if(l == r) return t[node];
    int mid = (l+r)>>1;
    if(targ <= mid) return qr(L[node], l, mid, targ);
    return qr(R[node], mid+1, r, targ);
}

void Init(){
    root[0] = 1;
    build(1, 1, N);
    return;
}

void TypeLetter(char L){
    root[cur_t] = nodecnt++;
    upd(root[cur_t-1], root[cur_t], 1, N, L);
    cur_t++;
    return;
}

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

char GetLetter(int P){
    return qr(root[cur_t-1], 1, N, P+1);
}

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