This documentation is automatically generated by online-judge-tools/verification-helper
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/set_xor_min
#include "../../template/template.hpp"
#include "../../structure/trie/binary-trie.hpp"
int main() {
int Q;
cin >> Q;
BinaryTrie< int, 29 > trie;
for(int i = 0; i < Q; i++) {
int t, x;
cin >> t >> x;
if(t == 0) {
if(trie.count(x) == 0) trie.add(x);
} else if(t == 1) {
if(trie.count(x) != 0) trie.erase(x);
} else {
cout << trie.min_element(x).first << "\n";
}
}
}
#line 1 "test/verify/yosupo-set-xor-min.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/set_xor_min
#line 1 "template/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;
struct IoSetup {
IoSetup() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout << fixed << setprecision(10);
cerr << fixed << setprecision(10);
}
} iosetup;
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
os << p.first << " " << p.second;
return os;
}
template <typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) {
is >> p.first >> p.second;
return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
for (int i = 0; i < (int)v.size(); i++) {
os << v[i] << (i + 1 != v.size() ? " " : "");
}
return os;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
for (T &in : v) is >> in;
return is;
}
template <typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {
return a < b && (a = b, true);
}
template <typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {
return a > b && (a = b, true);
}
template <typename T = int64>
vector<T> make_v(size_t a) {
return vector<T>(a);
}
template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type fill_v(T &t, const V &v) {
t = v;
}
template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type fill_v(T &t, const V &v) {
for (auto &e : t) fill_v(e, v);
}
template <typename F>
struct FixPoint : F {
explicit FixPoint(F &&f) : F(forward<F>(f)) {}
template <typename... Args>
decltype(auto) operator()(Args &&...args) const {
return F::operator()(*this, forward<Args>(args)...);
}
};
template <typename F>
inline decltype(auto) MFP(F &&f) {
return FixPoint<F>{forward<F>(f)};
}
#line 4 "test/verify/yosupo-set-xor-min.test.cpp"
#line 1 "structure/trie/binary-trie.hpp"
/**
* @brief Binary-Trie
*
*/
template <typename T, int MAX_LOG, typename D = int>
struct BinaryTrie {
public:
struct Node {
Node *nxt[2];
D exist;
vector<int> accept;
Node() : nxt{nullptr, nullptr}, exist(0) {}
};
Node *root;
explicit BinaryTrie() : root(new Node()) {}
explicit BinaryTrie(Node *root) : root(root) {}
void add(const T &bit, int idx = -1, D delta = 1, T xor_val = 0) {
root = add(root, bit, idx, MAX_LOG, delta, xor_val);
}
void erase(const T &bit, T xor_val = 0) { add(bit, -1, -1, xor_val); }
Node *find(const T &bit, T xor_val = 0) {
return find(root, bit, MAX_LOG, xor_val);
}
D count(const T &bit, T xor_val = 0) {
auto node = find(bit, xor_val);
return node ? node->exist : 0;
}
pair<T, Node *> min_element(T xor_val = 0) {
assert(root->exist > 0);
return kth_element(0, xor_val);
}
pair<T, Node *> max_element(T xor_val = 0) {
assert(root->exist > 0);
return kth_element(root->exist - 1, xor_val);
}
pair<T, Node *> kth_element(D k, T xor_val = 0) { // 0-indexed
assert(0 <= k && k < root->exist);
return kth_element(root, k, MAX_LOG, xor_val);
}
D count_less(const T &bit, T xor_val = 0) { // < bit
return count_less(root, bit, MAX_LOG, xor_val);
}
private:
virtual Node *clone(Node *t) { return t; }
Node *add(Node *t, T bit, int idx, int depth, D x, T xor_val,
bool need = true) {
if (need) t = clone(t);
if (depth == -1) {
t->exist += x;
if (idx >= 0) t->accept.emplace_back(idx);
} else {
bool f = (xor_val >> depth) & 1;
auto &to = t->nxt[f ^ ((bit >> depth) & 1)];
if (!to) to = new Node(), need = false;
to = add(to, bit, idx, depth - 1, x, xor_val, need);
t->exist += x;
}
return t;
}
Node *find(Node *t, T bit, int depth, T xor_val) {
if (depth == -1) {
return t;
} else {
bool f = (xor_val >> depth) & 1;
auto &to = t->nxt[f ^ ((bit >> depth) & 1)];
return to ? find(to, bit, depth - 1, xor_val) : nullptr;
}
}
pair<T, Node *> kth_element(Node *t, D k, int bit_index,
T xor_val) { // 0-indexed
if (bit_index == -1) {
return {0, t};
} else {
bool f = (xor_val >> bit_index) & 1;
if ((t->nxt[f] ? t->nxt[f]->exist : 0) <= k) {
auto ret =
kth_element(t->nxt[f ^ 1], k - (t->nxt[f] ? t->nxt[f]->exist : 0),
bit_index - 1, xor_val);
ret.first |= T(1) << bit_index;
return ret;
} else {
return kth_element(t->nxt[f], k, bit_index - 1, xor_val);
}
}
}
D count_less(Node *t, const T &bit, int bit_index, T xor_val) {
if (bit_index == -1) return 0;
D ret = 0;
bool f = (xor_val >> bit_index) & 1;
if ((bit >> bit_index & 1) and t->nxt[f]) ret += t->nxt[f]->exist;
if (t->nxt[f ^ (bit >> bit_index & 1)])
ret += count_less(t->nxt[f ^ (bit >> bit_index & 1)], bit, bit_index - 1,
xor_val);
return ret;
}
};
#line 6 "test/verify/yosupo-set-xor-min.test.cpp"
int main() {
int Q;
cin >> Q;
BinaryTrie< int, 29 > trie;
for(int i = 0; i < Q; i++) {
int t, x;
cin >> t >> x;
if(t == 0) {
if(trie.count(x) == 0) trie.add(x);
} else if(t == 1) {
if(trie.count(x) != 0) trie.erase(x);
} else {
cout << trie.min_element(x).first << "\n";
}
}
}
Env | Name | Status | Elapsed | Memory |
---|---|---|---|---|
g++ | almost_all_insert_00 | AC | 672 ms | 384 MB |
g++ | almost_all_query_00 | AC | 158 ms | 4 MB |
g++ | almost_all_query_close_00 | AC | 107 ms | 4 MB |
g++ | ans_big_00 | AC | 8 ms | 4 MB |
g++ | example_00 | AC | 8 ms | 4 MB |
g++ | max_ans_small_00 | AC | 585 ms | 210 MB |
g++ | max_random_00 | AC | 498 ms | 125 MB |
g++ | max_random_01 | AC | 478 ms | 126 MB |
g++ | max_random_02 | AC | 482 ms | 125 MB |
g++ | random_00 | AC | 353 ms | 101 MB |
g++ | random_01 | AC | 443 ms | 117 MB |
g++ | random_02 | AC | 42 ms | 20 MB |
clang++ | almost_all_insert_00 | AC | 727 ms | 384 MB |
clang++ | almost_all_query_00 | AC | 174 ms | 4 MB |
clang++ | almost_all_query_close_00 | AC | 120 ms | 4 MB |
clang++ | ans_big_00 | AC | 8 ms | 4 MB |
clang++ | example_00 | AC | 7 ms | 4 MB |
clang++ | max_ans_small_00 | AC | 624 ms | 210 MB |
clang++ | max_random_00 | AC | 497 ms | 126 MB |
clang++ | max_random_01 | AC | 501 ms | 126 MB |
clang++ | max_random_02 | AC | 503 ms | 125 MB |
clang++ | random_00 | AC | 372 ms | 101 MB |
clang++ | random_01 | AC | 461 ms | 117 MB |
clang++ | random_02 | AC | 46 ms | 20 MB |