oj.uz

Submission #923756

# Submission time Handle Problem Language Result Execution time Memory
923756 2024-02-07T17:36:05 Z Camillus The Potion of Great Power (CEOI20_potion) C++17
100 / 100
 2582 ms 195764 KB 
/// @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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 2 ms 856 KB Output is correct
3 Correct 1 ms 856 KB Output is correct
4 Correct 16 ms 11016 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 69216 KB Output is correct
2 Correct 364 ms 68816 KB Output is correct
3 Correct 336 ms 106256 KB Output is correct
4 Correct 1628 ms 178368 KB Output is correct
5 Correct 836 ms 187472 KB Output is correct
6 Correct 1658 ms 193152 KB Output is correct
7 Correct 553 ms 109720 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 70004 KB Output is correct
2 Correct 1910 ms 192712 KB Output is correct
3 Correct 1432 ms 195392 KB Output is correct
4 Correct 2162 ms 193060 KB Output is correct
5 Correct 440 ms 69200 KB Output is correct
6 Correct 2317 ms 193036 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 3440 KB Output is correct
2 Correct 76 ms 7916 KB Output is correct
3 Correct 112 ms 8680 KB Output is correct
4 Correct 493 ms 8424 KB Output is correct
5 Correct 430 ms 7928 KB Output is correct
6 Correct 99 ms 7144 KB Output is correct
7 Correct 392 ms 8164 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 856 KB Output is correct
3 Correct 2 ms 856 KB Output is correct
4 Correct 1 ms 856 KB Output is correct
5 Correct 16 ms 11016 KB Output is correct
6 Correct 332 ms 69216 KB Output is correct
7 Correct 364 ms 68816 KB Output is correct
8 Correct 336 ms 106256 KB Output is correct
9 Correct 1628 ms 178368 KB Output is correct
10 Correct 836 ms 187472 KB Output is correct
11 Correct 1658 ms 193152 KB Output is correct
12 Correct 553 ms 109720 KB Output is correct
13 Correct 360 ms 70004 KB Output is correct
14 Correct 1910 ms 192712 KB Output is correct
15 Correct 1432 ms 195392 KB Output is correct
16 Correct 2162 ms 193060 KB Output is correct
17 Correct 440 ms 69200 KB Output is correct
18 Correct 2317 ms 193036 KB Output is correct
19 Correct 35 ms 3440 KB Output is correct
20 Correct 76 ms 7916 KB Output is correct
21 Correct 112 ms 8680 KB Output is correct
22 Correct 493 ms 8424 KB Output is correct
23 Correct 430 ms 7928 KB Output is correct
24 Correct 99 ms 7144 KB Output is correct
25 Correct 392 ms 8164 KB Output is correct
26 Correct 811 ms 112252 KB Output is correct
27 Correct 1492 ms 195764 KB Output is correct
28 Correct 1369 ms 108480 KB Output is correct
29 Correct 1751 ms 179316 KB Output is correct
30 Correct 2582 ms 192100 KB Output is correct
31 Correct 2084 ms 193132 KB Output is correct
32 Correct 2387 ms 191864 KB Output is correct