oj.uz

Submission #923749

# Submission time Handle Problem Language Result Execution time Memory
923749 2024-02-07T17:23:54 Z Camillus The Potion of Great Power (CEOI20_potion) C++17
70 / 100
 3000 ms 162884 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 {
        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 1 ms 596 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 856 KB Output is correct
4 Correct 16 ms 10800 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 60016 KB Output is correct
2 Correct 329 ms 61032 KB Output is correct
3 Correct 320 ms 89444 KB Output is correct
4 Correct 1870 ms 147724 KB Output is correct
5 Correct 811 ms 154356 KB Output is correct
6 Correct 2678 ms 161116 KB Output is correct
7 Correct 603 ms 91916 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 60712 KB Output is correct
2 Correct 2075 ms 159732 KB Output is correct
3 Correct 1398 ms 161972 KB Output is correct
4 Correct 2343 ms 160328 KB Output is correct
5 Correct 437 ms 62152 KB Output is correct
6 Correct 2510 ms 160200 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 3280 KB Output is correct
2 Correct 82 ms 8136 KB Output is correct
3 Correct 119 ms 6600 KB Output is correct
4 Correct 735 ms 7112 KB Output is correct
5 Correct 728 ms 8392 KB Output is correct
6 Correct 111 ms 5576 KB Output is correct
7 Correct 579 ms 6344 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 1 ms 596 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 856 KB Output is correct
5 Correct 16 ms 10800 KB Output is correct
6 Correct 325 ms 60016 KB Output is correct
7 Correct 329 ms 61032 KB Output is correct
8 Correct 320 ms 89444 KB Output is correct
9 Correct 1870 ms 147724 KB Output is correct
10 Correct 811 ms 154356 KB Output is correct
11 Correct 2678 ms 161116 KB Output is correct
12 Correct 603 ms 91916 KB Output is correct
13 Correct 305 ms 60712 KB Output is correct
14 Correct 2075 ms 159732 KB Output is correct
15 Correct 1398 ms 161972 KB Output is correct
16 Correct 2343 ms 160328 KB Output is correct
17 Correct 437 ms 62152 KB Output is correct
18 Correct 2510 ms 160200 KB Output is correct
19 Correct 37 ms 3280 KB Output is correct
20 Correct 82 ms 8136 KB Output is correct
21 Correct 119 ms 6600 KB Output is correct
22 Correct 735 ms 7112 KB Output is correct
23 Correct 728 ms 8392 KB Output is correct
24 Correct 111 ms 5576 KB Output is correct
25 Correct 579 ms 6344 KB Output is correct
26 Correct 960 ms 97116 KB Output is correct
27 Correct 1720 ms 162884 KB Output is correct
28 Correct 1678 ms 93064 KB Output is correct
29 Correct 1919 ms 146516 KB Output is correct
30 Execution timed out 3077 ms 159332 KB Time limit exceeded
31 Halted 0 ms 0 KB -