제출 #218974

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
218974		dung11112003	크레이피쉬 글쓰는 기계 (IOI12_scrivener)	C++11	34 / 100	166 ms	158456 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 = 5e6 + 10;

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

node* build(int lo, int hi)
{
    if (lo == hi)
    {
        return ++pt;
    }
    int mid = (lo + hi) / 2;
    node *cur = ++pt;
    cur->left = build(lo, mid);
    cur->right = build(mid + 1, hi);
    return cur;
}

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

node *add(node *x, int lo, int hi)
{
    if (lo == hi)
    {
        ++pt;
        *pt = node(1, val);
        return pt;
    }
    int mid = (lo + hi) / 2;
    node *cur = ++pt;
    if (x->left->cnt < mid - lo + 1)
    {
        cur->left = add(x->left, lo, mid);
        cur->right = x->right;
    }
    else
    {
        cur->left = x->left;
        cur->right = add(x->right, mid + 1, hi);
    }
    cur->cnt = cur->left->cnt + cur->right->cnt;
    return cur;
}

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

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

char query(node* x, int lo, int hi)
{
    if (lo == hi && lo == idx)
    {
        return x->c;
    }
    int mid = (lo + hi) / 2;
    if (idx <= mid)
    {
        return query(x->left, lo, mid);
    }
    return query(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: 0 / 26
• Subtask 5: 0 / 40