Submission #290220

#	Time	Username	Problem	Language	Result	Execution time	Memory
290220		stoyan_malinin	Crayfish scrivener (IOI12_scrivener)	C++14	34 / 100	570 ms	262148 KiB

scrivener

//#include "grader.cpp"

#include <vector>
#include <iostream>

using namespace std;

const int MAXN = 1e6 + 5;

struct SegmentTree
{
    char val;
    SegmentTree *L, *R;

    void build(int l, int r)
    {
        if(l==r) return;

        L = new SegmentTree();
        R = new SegmentTree();

        L->build(l, (l+r)/2);
        R->build((l+r)/2+1, r);
    }

    void update(int q, char c, int l, int r, SegmentTree *other)
    {
        val = other->val;

        if(l==r && q==l)
        {
            val = c;
            return;
        }

        if(l<=q && q<=(l+r)/2)
        {
            L = new SegmentTree();
            L->update(q, c, l, (l+r)/2, other->L);
        }
        else
        {
            L = other->L;
        }

        if((l+r)/2+1<=q && q<=r)
        {
            R = new SegmentTree();
            R->update(q, c, (l+r)/2+1, r, other->R);
        }
        else
        {
            R = other->R;
        }
    }

    char getChar(int q, int l, int r)
    {
        if(l==r) return val;

        if(l<=q && q<=(l+r)/2) return L->getChar(q, l, (l+r)/2);
        return R->getChar(q, (l+r)/2+1, r);
    }
};

struct String
{
    int sz;
    SegmentTree *s;

    String(){}
    String(int sz)
    {
        this->sz = sz;
        this->s = new SegmentTree();
    }
};

int COMMAND = 0;
String state[MAXN];

void Init()
{
    state[0] = String(0);
    state[0].s->build(0, MAXN);
}

void TypeLetter(char L)
{
    COMMAND++;
    state[COMMAND].sz = state[COMMAND-1].sz + 1;

    state[COMMAND].s = new SegmentTree();
    state[COMMAND].s->update(state[COMMAND].sz-1, L, 0, MAXN, state[COMMAND-1].s);
}

void UndoCommands(int U)
{
    COMMAND++;
    state[COMMAND] = state[COMMAND-1-U];
}

char GetLetter(int P)
{
    return state[COMMAND].s->getChar(P, 0, MAXN);
}

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