Submission #361293

#	Time	Username	Problem	Language	Result	Execution time	Memory
361293		bigDuck	Crayfish scrivener (IOI12_scrivener)	C++14	34 / 100	610 ms	262148 KiB

scrivener

#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount


int tmp=0;
struct nod{

    nod *l, *r;
    char c;
    int ln;
    nod(nod *l, nod *r){
        this->l=l;
        this->r=r;
        this->ln=l->ln+r->ln;
    }
    nod(char c){
    if(c=='-'){
        this->c=c;
        this->ln=0;
        this->r=NULL;
        this->l=NULL;
        return;
    }
    this->ln=1;
    this->l=NULL;
    this->r=NULL;
    this->c=c;
    }
} *ver[1000010];




nod *add(nod *v, int l, int r, char c){

    if(l==r){
        return new nod(c);
    }
    int mid=(l+r)>>1ll;
    if( (v->l->ln)==(mid-l+1) ){
        return new nod(v->l, add(v->r, mid+1, r, c) );
    }
    else{
        return new nod(add(v->l, l, mid, c), v->r );
    }

}



char get_char(nod *v, int l, int r, int p){

    if(l==r){
        return v->c;
    }

    int mid=(l+r)>>1ll;
    if(p<=mid){
        return get_char(v->l, l, mid, p);
    }
    else{
        return get_char(v->r, mid+1, r, p);
    }
}



nod *build(int l, int r){
    if(l==r){
        return new nod('-');
    }
    int mid=(l+r)>>1ll;
    return new nod(build(l, mid), build(mid+1, r) );
}


void Init() {
    ver[0]=build(1, 1000000);
}




void TypeLetter(char L) {
    ver[tmp+1]=add(ver[tmp], 1, 1000000, L);
    tmp++;
}

void UndoCommands(int U){
    ver[tmp+1]=ver[tmp-U];
    tmp++;
}

char GetLetter(int P){
    return get_char(ver[tmp], 1, 1000000, P+1);
}

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