Submission #27742

#TimeUsernameProblemLanguageResultExecution timeMemory
27742zoomswkCrayfish scrivener (IOI12_scrivener)C++14
100 / 100
596 ms208208 KiB
#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);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...