Submission #923756

#	Time	Username	Problem	Language	Result	Execution time	Memory
923756		Camillus	The Potion of Great Power (CEOI20_potion)	C++17	100 / 100	2582 ms	195764 KiB

potion

/// @author Camillus
#include <bits/stdc++.h>
using namespace std;

namespace treap {
    mt19937_64 rnd(228);

    int rand(int n) {
        return rnd() % n;
    }

    struct Node {
        pair<int, int> key;
        int size = 0;

        int left = 0;
        int right = 0;

        Node() {}

        Node(pair<int, int> key) : key(key) {
            size = 1;
        }
    };

    vector<Node> tree = { Node() };

    int new_node(pair<int, int> key) {
        tree.emplace_back(key);
        return (int)tree.size() - 1;
    }

    int clone_node(int node) {
        tree.push_back(tree[node]);
        return (int)tree.size() - 1;
    }

    void pull(int node) {
        tree[node].size = 1;
        tree[node].size += tree[tree[node].left].size;
        tree[node].size += tree[tree[node].right].size;
    }

    pair<int, int> split(int node, pair<int, int> key) {
        if (node == 0) {
            return {0, 0};
        }

        if (tree[node].key < key) {
            auto [first, second] = split(tree[node].right, key);
            node = clone_node(node);
            tree[node].right = first;
            pull(node);
            return {node, second};
        } else {
            auto [first, second] = split(tree[node].left, key);
            node = clone_node(node);
            tree[node].left = second;
            pull(node);
            return {first, node};
        }
    }

    int merge(int first, int second) {
        if (first == 0 || second == 0) {
            return first + second;
        }

        if (rand(tree[first].size + tree[second].size) < tree[first].size) {
            first = clone_node(first);
            tree[first].right = merge(tree[first].right, second);
            pull(first);
            return first;
        } else {
            second = clone_node(second);
            tree[second].left = merge(first, tree[second].left);
            pull(second);
            return second;
        }
    }

    bool contains(int node, pair<int, int> key) {
        if (node == 0) {
            return false;
        }

        if (tree[node].key == key) {
            return true;
        } else if (tree[node].key < key) {
            return contains(tree[node].right, key);
        } else {
            return contains(tree[node].left, key);
        }
    }

    int insert(int node, pair<int, int> key) {
        auto [first, second] = split(node, key);
        return merge(first, merge(new_node(key), second));
    }

    int remove(int node, pair<int, int> key) {
        auto [first, second] = split(node, key);
        auto key2 = key;
        key2.second++;
        second = split(second, key2).second;
        return merge(first, second);
    }

    vector<pair<int, int>> collect(int node) {
        vector<pair<int, int>> result;

        auto dfs = [&](auto &&self, int current) -> void {
            if (current == 0) {
                return;
            }
            self(self, tree[current].left);
            result.push_back(tree[current].key);
            self(self, tree[current].right);
        };

        dfs(dfs, node);

        return result;
    }
} // namespace treap

vector<map<int, int>> versions;
vector<int> h;
int n;

void init(int N, int D, int H[]) {
    n = N;
    h = vector<int>(H, H + N);
}

void curseChanges(int U, int A[], int B[]) {
    versions.resize(n);
    for (int i = 0; i < n; i++) {
        versions[i][0] = 0;
    }

    for (int i = 1; i <= U; i++) {
        int a = A[i - 1];
        int b = B[i - 1];

        int node_a = prev(versions[a].end())->second;
        int node_b = prev(versions[b].end())->second;

        if (treap::contains(node_a, pair(h[b], b))) {
            versions[a][i] = treap::remove(node_a, pair(h[b], b));
            versions[b][i] = treap::remove(node_b, pair(h[a], a));
        } else {
            versions[a][i] = treap::insert(node_a, pair(h[b], b));
            versions[b][i] = treap::insert(node_b, pair(h[a], a));
        }
    }
}

int question(int X, int Y, int V) {
    int node_a = prev(versions[X].upper_bound(V))->second;
    int node_b = prev(versions[Y].upper_bound(V))->second;

    vector<pair<int, int>> first;
    for (auto x : treap::collect(node_a)) {
        x.second = 0;
        first.push_back(x);
    }

    vector<pair<int, int>> second;
    for (auto x : treap::collect(node_b)) {
        x.second = 1;
        second.push_back(x);
    }

    vector<pair<int, int>> A(first.size() + second.size());
    merge(first.begin(), first.end(), second.begin(), second.end(), A.begin());

    int ans = 1'000'000'000;

    for (int i = 0; i + 1 < (int)A.size(); i++) {
        if (A[i].second != A[i + 1].second) {
            ans = min(ans, A[i + 1].first - A[i].first);
        }
    }
    return ans;
}

#ifdef LOCAL
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init(6, 5, vector<int>({2, 42, 1000, 54, 68, 234}).data());
    curseChanges(
        11,
        vector<int>({0, 2, 3, 3, 3, 1, 5, 0, 3, 1, 3}).data(),
        vector<int>({1, 0, 4, 5, 5, 3, 3, 5, 0, 3, 5}).data()
    );
    debug(question(0, 3, 4));
    debug(question(3, 0, 8));
    debug(question(0, 5, 5));
    debug(question(3, 0, 11));
    return 0;
}
#endif

• Subtask 1: 0 / 0
• Subtask 2: 17 / 17
• Subtask 3: 14 / 14
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 30 / 30