oj.uz

Submission #923752

# Submission time Handle Problem Language Result Execution time Memory
923752 2024-02-07T17:25:40 Z Camillus The Potion of Great Power (CEOI20_potion) C++17
70 / 100
 3000 ms 162904 KB 
/// @author Camillus
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;

namespace treap {
    mt19937_64 rnd(52);

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

    struct Node {
        int key = 0;
        int size = 0;

        int left = 0;
        int right = 0;

        Node() {}

        Node(int key) : key(key) {
            size = 1;
        }
    };

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

    int new_node(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, 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, 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, int key) {
        auto [first, second] = split(node, key);
        return merge(first, merge(new_node(key), second));
    }

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

    vector<int> collect(int node) {
        vector<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, b)) {
            versions[a][i] = treap::remove(node_a, b);
            versions[b][i] = treap::remove(node_b, a);
        } else {
            versions[a][i] = treap::insert(node_a, b);
            versions[b][i] = treap::insert(node_b, 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;

    auto first = treap::collect(node_a);
    auto second = treap::collect(node_b);

    vector<pair<int, bool>> A;

    for (int i : first) {
        A.emplace_back(h[i], false);
    }

    for (int i : second) {
        A.emplace_back(h[i], true);
    }

    sort(A.begin(), A.end());

    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 2 ms 856 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 18 ms 11012 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 60800 KB Output is correct
2 Correct 327 ms 61268 KB Output is correct
3 Correct 321 ms 89360 KB Output is correct
4 Correct 1902 ms 146800 KB Output is correct
5 Correct 817 ms 154212 KB Output is correct
6 Correct 2747 ms 160424 KB Output is correct
7 Correct 616 ms 92040 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 61876 KB Output is correct
2 Correct 2053 ms 158740 KB Output is correct
3 Correct 1440 ms 162500 KB Output is correct
4 Correct 2371 ms 160644 KB Output is correct
5 Correct 417 ms 62996 KB Output is correct
6 Correct 2481 ms 159232 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 3284 KB Output is correct
2 Correct 83 ms 7344 KB Output is correct
3 Correct 132 ms 8392 KB Output is correct
4 Correct 740 ms 6600 KB Output is correct
5 Correct 726 ms 6856 KB Output is correct
6 Correct 106 ms 6856 KB Output is correct
7 Correct 599 ms 8136 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 856 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 2 ms 600 KB Output is correct
5 Correct 18 ms 11012 KB Output is correct
6 Correct 322 ms 60800 KB Output is correct
7 Correct 327 ms 61268 KB Output is correct
8 Correct 321 ms 89360 KB Output is correct
9 Correct 1902 ms 146800 KB Output is correct
10 Correct 817 ms 154212 KB Output is correct
11 Correct 2747 ms 160424 KB Output is correct
12 Correct 616 ms 92040 KB Output is correct
13 Correct 310 ms 61876 KB Output is correct
14 Correct 2053 ms 158740 KB Output is correct
15 Correct 1440 ms 162500 KB Output is correct
16 Correct 2371 ms 160644 KB Output is correct
17 Correct 417 ms 62996 KB Output is correct
18 Correct 2481 ms 159232 KB Output is correct
19 Correct 38 ms 3284 KB Output is correct
20 Correct 83 ms 7344 KB Output is correct
21 Correct 132 ms 8392 KB Output is correct
22 Correct 740 ms 6600 KB Output is correct
23 Correct 726 ms 6856 KB Output is correct
24 Correct 106 ms 6856 KB Output is correct
25 Correct 599 ms 8136 KB Output is correct
26 Correct 955 ms 96052 KB Output is correct
27 Correct 1739 ms 162904 KB Output is correct
28 Correct 1718 ms 90920 KB Output is correct
29 Correct 1981 ms 147300 KB Output is correct
30 Execution timed out 3020 ms 159652 KB Time limit exceeded
31 Halted 0 ms 0 KB -