Submission #78559

#	Time	Username	Problem	Language	Result	Execution time	Memory
78559		Charis02	Crayfish scrivener (IOI12_scrivener)	C++14	34 / 100	1029 ms	123248 KiB

scrivener

#include<stdio.h>
#include<algorithm>
#define ll int
#define rep(i,a,b) for(int i = a;i < b;i++)
#define N 1000004

using namespace std;

ll root;
ll countt = 0;
ll dp[N][21];
ll ldp[N][21];
ll length[N];
bool isupdate[N];
char ans[N];

ll newNode()
{
    isupdate[countt] = false;
    length[countt] = 0;

    countt++;

    return countt-1;
}

void Init()
{
    root = newNode();
}

bool ison(ll x,ll i)
{
    return (bool)(x&(1 << i));
}

ll jump(ll cur,ll x)
{
    if(dp[cur][x])
        return dp[cur][x];

    return dp[cur][x] = jump(jump(cur,x-1),x-1);
}

ll ancestor(ll cur,ll x)
{
    if(x == 0)
        return cur;

    ll res = cur;

    rep(i,0,20)
    {
        if(ison(x,i))
        {
            res = jump(res,i);
        }
    }

    return res;
}


ll letterjump(ll cur,ll x)
{
    if(ldp[cur][x])
        return ldp[cur][x];

    return ldp[cur][x] = letterjump(letterjump(cur,x-1),x-1);
}

ll letterancestor(ll cur,ll x)
{
    if(x == 0)
        return cur;

    ll res = cur;

    rep(i,0,20)
    {
        if(ison(x,i))
        {
            res = letterjump(res,i);
        }
    }

    return res;
}

void TypeLetter(char c)
{
    ll p = root;
    root = newNode();
    dp[root][0] = p;

    if(isupdate[p])
    {
        ldp[root][0] = ldp[p][0];
    }
    else
    {
        ldp[root][0] = p;
    }

    length[root] = length[p] + 1;
    ans[root] = c;

    return;
}

void UndoCommands(ll x)
{
    ll p = root;
    ll rp = ancestor(p,x);

    root = newNode();
    dp[root][0] = p;

    if(isupdate[rp])
    {
        ldp[root][0] = ldp[rp][0];
    }
    else
    {
        ldp[root][0] = rp;
    }

    isupdate[root] = true;
    length[root] = length[rp];
    ans[root] = '0';

    return;
}

char GetLetter(int P)
{
    return ans[letterancestor(root,(length[root]) - P - (ll)(!isupdate[root]))];
}

/*
int main()
{
    n = read();

    rep(i,0,n)
    {
        type = gc();

        while(type < 'A' || type > 'Z')
            type = gc();

        if(type == 'T')
        {
            c = gc();

            while(c < 'a' || c > 'z')
                c = gc();

            typechar(c,root);
        }
        else if(type == 'U')
        {
            d = read();
            undo(d,root);
        }
        else
        {
            d = read();

            printf("%c\n",(letterancestor(root,(root -> length) - d - (ll)(!(root -> isupdate))) -> ans));
        }
    }

    return 0;
}*/

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