/// @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
Compilation message
potion.cpp:3:27: error: '#pragma GCC optimize' string is badly formed
3 | #pragma GCC optimize("O3");
| ^
