Submission #218985

#	Time	Username	Problem	Language	Result	Execution time	Memory
218985		dung11112003	Crayfish scrivener (IOI12_scrivener)	C++11	100 / 100	503 ms	211064 KiB

scrivener

#include <bits/stdc++.h>

#define taskname ""
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define for0(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef complex <ld> cd;
typedef vector <cd> vcd;
typedef vector <int> vi;

template<class T> using v2d = vector <vector <T> >;
template<class T> bool uin(T &a, T b)
{
    return a > b ? (a = b, true) : false;
}
template<class T> bool uax(T &a, T b)
{
    return a < b ? (a = b, true) : false;
}

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

const int maxS = 1e6 + 10;
const int maxT = 20e6 + 10;

struct node
{
    int left, right;
    char c;
    node() {}
    node(char c) : c(c) {}
} f[maxT];
int cnt[maxS], pos[maxS], pt = 0, ver = 0;
int idx;
char val;

int build(int lo, int hi)
{
    if (lo == hi)
    {
        return ++pt;
    }
    int mid = (lo + hi) / 2;
    int cur = ++pt;
    f[cur].left = build(lo, mid);
    f[cur].right = build(mid + 1, hi);
    return cur;
}

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

int add(int x, int lo, int hi)
{
    if (lo == hi && lo == idx)
    {
        f[++pt] = node(val);
        return pt;
    }
    int mid = (lo + hi) / 2;
    int cur = ++pt;
    if (idx <= mid)
    {
        f[cur].left = add(f[x].left, lo, mid);
        f[cur].right = f[x].right;
    }
    else
    {
        f[cur].left = f[x].left;
        f[cur].right = add(f[x].right, mid + 1, hi);
    }
    return cur;
}

void TypeLetter(char L)
{
    val = L;
    idx = cnt[ver + 1] = cnt[ver] + 1;
    pos[ver + 1] = add(pos[ver], 1, 1000000);
    ++ver;
}

void UndoCommands(int U)
{
    ++pt;
    f[pt] = f[pos[ver - U]];
    cnt[ver + 1] = cnt[ver - U];
    pos[++ver] = pt;
}

char query(int x, int lo, int hi)
{
    if (lo == hi && lo == idx)
    {
        return f[x].c;
    }
    int mid = (lo + hi) / 2;
    if (idx <= mid)
    {
        return query(f[x].left, lo, mid);
    }
    return query(f[x].right, mid + 1, hi);
}

char GetLetter(int P)
{
    idx = ++P;
    return query(pos[ver], 1, 1000000);
}

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