Submission #290268

#	Time	Username	Problem	Language	Result	Execution time	Memory
290268		stoyan_malinin	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	594 ms	209564 KiB

scrivener

//#include "grader.cpp"

#include <vector>
#include <cstring>
#include <iostream>

using namespace std;

const int MAXN = 1e6 + 5;
const long long onlyOnes = (1LL<<61) - 1;

long long mask1, mask2, mask3;

struct SegmentTree
{
    int nodes = 0;
    long long tree[MAXN*25];
    //0-24|25-49|50-55

    SegmentTree()
    {
        memset(this->tree, 0, sizeof(this->tree));
    }

    int getNode()
    {
        nodes++;
        return nodes - 1;
    }

    void encodeNum(long long &x, long long num, int type)
    {
        long long mask, shift;
        if(type==1) mask = mask1, shift = 0;
        else if(type==2) mask = mask2, shift = 25;
        else if(type==3) mask = mask3, shift = 50;

        x &= (onlyOnes - mask);
        x |= ((num<<shift)&mask);
    }

    long long readNum(long long x, int type)
    {
        if(type==1) return (x&mask1);
        if(type==2) return ((x&mask2)>>25);
        if(type==3) return ((x&mask3)>>50);
    }

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

        int L = getNode();
        int R = getNode();

        encodeNum(tree[node], L, 1);
        encodeNum(tree[node], R, 2);

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

    void update(int q, int node, char c, int l, int r, int other)
    {
        if(l==r)
        {
            encodeNum(tree[node], c-'a', 3);
            return;
        }

        int L;
        if(l<=q && q<=(l+r)/2)
        {
            L = getNode();
            update(q, L, c, l, (l+r)/2, readNum(tree[other], 1));
        }
        else
        {
            L = readNum(tree[other], 1);
        }
        encodeNum(tree[node], L, 1);

        int R;
        if((l+r)/2+1<=q && q<=r)
        {
            R = getNode();
            update(q, R, c, (l+r)/2+1, r, readNum(tree[other], 2));
        }
        else
        {
            R = readNum(tree[other], 2);
        }
        encodeNum(tree[node], R, 2);
    }

    char getChar(int q, int node, int l, int r)
    {
        if(l==r) return char(readNum(tree[node], 3)+'a');

        if(l<=q && q<=(l+r)/2) return getChar(q, readNum(tree[node], 1), l, (l+r)/2);
        return getChar(q, readNum(tree[node], 2), (l+r)/2+1, r);
    }
};

struct String
{
    int sz;
    int root;

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

SegmentTree *T = new SegmentTree();

int COMMAND = 0;
String state[MAXN];

void Init()
{
    mask1 = 0;
    for(int bit = 0;bit<=24;bit++) mask1 += (1LL<<bit);

    mask2 = 0;
    for(int bit = 25;bit<=49;bit++) mask2 += (1LL<<bit);

    mask3 = 0;
    for(int bit = 50;bit<=55;bit++) mask3 += (1LL<<bit);

    state[0] = String(0);
    state[0].root = T->getNode();

    T->build(state[0].root, 0, MAXN);
}

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

    state[COMMAND].root = T->getNode();
    T->update(state[COMMAND].sz-1, state[COMMAND].root, L, 0, MAXN, state[COMMAND-1].root);
}

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

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

Compilation message (stderr)

scrivener.cpp: In member function 'long long int SegmentTree::readNum(long long int, int)':
scrivener.cpp:47:5: warning: control reaches end of non-void function [-Wreturn-type]
   47 |     }
      |     ^

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