Submission #1176069

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176069		_uros9	Crayfish scrivener (IOI12_scrivener)	C++20	100 / 100	331 ms	239100 KiB

scrivener

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const int N=1000009;

struct Cvor{
    int L,R,val;
    Cvor(){L=0;R=0;val=0;}
    Cvor(int L,int R,int val){this->L=L;this->R=R;this->val=val;}
};
int i;
Cvor seg[20000000];
int indx=0;
int root[N];

void upd(int old,int node,int l,int d,int ind,int val){
    int s=l+d>>1;
    if(l==d&&d==ind){
        seg[node]=Cvor(0,0,val);
        return;
    }
    if(ind<=s){
        seg[node].L=++indx;
        seg[node].R=seg[old].R;
        upd(seg[old].L,indx,l,s,ind,val);
    }
    else{
        seg[node].R=++indx;
        seg[node].L=seg[old].L;
        upd(seg[old].R,indx,s+1,d,ind,val);
    }
}
int siz(int node,int l,int d){
    if(l==d) return l;
    int s=l+d>>1;
    if(seg[node].R) return siz(seg[node].R,s+1,d);
    return siz(seg[node].L,l,s);
}
int query(int node,int l,int d,int ind){
    if(l==d) return seg[node].val;
    int s=l+d>>1;
    if(ind<=s) return query(seg[node].L,l,s,ind);
    return query(seg[node].R,s+1,d,ind);
}

void Init(){
    i=0;
    return;
}
void TypeLetter(char L){
    i++;
    root[i]=++indx;
    upd(root[i-1],root[i],0,N,siz(root[i-1],0,N)+1,L-'a');
    return;
}
void UndoCommands(int U){
    i++;
    root[i]=root[i-U-1];
    return;
}
char GetLetter(int P){
    return char('a'+query(root[i],0,N,P+1));
}

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