Submission #999894

#	Time	Username	Problem	Language	Result	Execution time	Memory
999894		shmax	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	269 ms	205788 KiB

scrivener

#include <bits/stdc++.h>

//#pragma GCC optimize("O3")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization ("unroll-loops")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,sse4,popcnt")

using namespace std;
#define len(x) (int) x.size()
using i32 = int32_t;

template<typename T>
using vec = vector<T>;


struct node {
    int cnt;
    int left, right;

    explicit node(int val) : left(-1), right(-1) {
        if (val != -1) cnt = -val;
        else cnt = 0;
    }

    node() = default;

};

const int maxNodes = 1e8 + 5;
node nodes[maxNodes];
int cnt_nodes = 0;


void fetch(int id) {
    if (id == -1) return;
    nodes[id].cnt = 0;
    if (nodes[id].left != -1) nodes[id].cnt += (nodes[nodes[id].left].cnt < 0) + max(0, nodes[nodes[id].left].cnt);
    if (nodes[id].right != -1) nodes[id].cnt += (nodes[nodes[id].right].cnt < 0) + max(0, nodes[nodes[id].right].cnt);
}

int add_node(int x) {
    nodes[cnt_nodes] = node(x);
    return cnt_nodes++;
}

int build(int l, int r) {
    if (l == r) {
        return add_node(-1);
    }
    int m = (l + r) / 2;
    int new_root = add_node(-1);
    int id = build(l, m);
    nodes[new_root].left = id;
    id = build(m + 1, r);
    nodes[new_root].right = id;
    fetch(new_root);
    return new_root;
}

int update(int v, int l, int r, int pos, int val) {
    if (l == r) {
        return add_node(val);
    }
    int m = (l + r) / 2;
    int new_node = add_node(-1);
    if (pos <= m) {
        int left = update(nodes[v].left, l, m, pos, val);
        nodes[new_node].left = left;
        nodes[new_node].right = nodes[v].right;
    } else {
        int right = update(nodes[v].right, m + 1, r, pos, val);
        nodes[new_node].right = right;
        nodes[new_node].left = nodes[v].left;
    }
    fetch(new_node);
    return new_node;
}

int get(int v, int l, int r, int pos) {
    if (l == r) {
        return -nodes[v].cnt;
    }
    int m = (l + r) / 2;
    if (pos <= m) {
        return get(nodes[v].left, l, m, pos);
    } else {
        return get(nodes[v].right, m + 1, r, pos);
    }
}

const int maxN = 1e6 + 5;
vec<int> roots;


void Init() {
    roots.push_back(build(0, maxN));
}

void TypeLetter(char L) {
    int last = roots.back();
    int new_n = update(last, 0, maxN, nodes[last].cnt, L);
    roots.push_back(new_n);
}

void UndoCommands(i32 U) {
    int pr = roots[len(roots) - U - 1];
    roots.push_back(pr);
}

char GetLetter(i32 P) {
    return get(roots.back(), 0, maxN, P);
}

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