Submission #377090

#	Time	Username	Problem	Language	Result	Execution time	Memory
377090		ponytail	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	549 ms	211140 KiB

scrivener

#include "bits/stdc++.h"
#define pb push_back
using namespace std;
struct node{
    int l,r;
    char val;
};
const int MAXN = 23931670;
node a[MAXN];
int sto=-1;
vector<int>version_roots;
vector<int>version_wordlens;
int cnt=0;
int build(int L,int R){
    int next_node=++sto;
    if(L==R){
        a[next_node].val='.';
        return next_node;
    }
    int mid=(L+R)/2;
    a[next_node].l=build(L,mid);
    a[next_node].r=build(mid+1,R);
    return next_node;
}
int update(int node,char yes,int L,int R,int tar){
    int next_node=++sto;
    if(L==R){
        a[next_node].val=yes;
        return next_node;
    }
    int mid=(L+R)/2;
    if(tar<=mid){
        a[next_node].l=update(a[node].l,yes,L,mid,tar);
        a[next_node].r=a[node].r;
    }
    else{
        a[next_node].l=a[node].l;
        a[next_node].r=update(a[node].r,yes,mid+1,R,tar);
    }
    return next_node;
}
char query(int node,int L,int R,int tar){
    if(L==R){
        return a[node].val;
    }
    int mid=(L+R)/2;
    if(tar<=mid){
        return query(a[node].l,L,mid,tar);
    }
    else{
        return query(a[node].r,mid+1,R,tar);
    }
}
void Init(){
    build(1,1000000);
    version_roots.pb(0);
    version_wordlens.pb(0);
}
void TypeLetter(char L){
    cnt++;
    version_roots.pb(sto+1);
    version_wordlens.pb(version_wordlens[cnt-1]+1);
    update(version_roots[cnt-1],L,1,1000000,version_wordlens[cnt]);
}
void UndoCommands(int U){
    cnt++;
    version_roots.pb(sto+1);
    version_wordlens.pb(version_wordlens[cnt-U-1]);
    int next_node=++sto;
    a[next_node].l=a[version_roots[cnt-U-1]].l;
    a[next_node].r=a[version_roots[cnt-U-1]].r;
}
char GetLetter(int P){
    P++;
    return query(version_roots[cnt],1,1000000,P);
}

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