제출 #290260

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
290260		stoyan_malinin	크레이피쉬 글쓰는 기계 (IOI12_scrivener)	C++14	34 / 100	1059 ms	200556 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;

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 lBit, int rBit)
    {
        for(int bit = lBit;bit<=rBit;bit++)
        {
            x &= (onlyOnes - (1LL<<bit));
            x |= ((num>>(bit-lBit)&1LL)<<bit);
        }
    }

    long long readNum(long long x, int lBit, int rBit)
    {
        int res = 0;
        for(int bit = lBit;bit<=rBit;bit++)
        {
            res += (((x>>bit)&1LL)<<(bit-lBit));
        }

        return res;
    }

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

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

        encodeNum(tree[node], L, 0, 24);
        encodeNum(tree[node], R, 25, 49);

        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', 50, 55);
            return;
        }

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

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

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

        if(l<=q && q<=(l+r)/2) return getChar(q, readNum(tree[node], 0, 24), l, (l+r)/2);
        return getChar(q, readNum(tree[node], 25, 49), (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()
{
    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);
}

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