結果
問題 | No.2195 AND Set |
ユーザー | nono00 |
提出日時 | 2023-01-20 21:53:45 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 796 ms / 2,000 ms |
コード長 | 2,669 bytes |
コンパイル時間 | 2,354 ms |
コンパイル使用メモリ | 217,324 KB |
実行使用メモリ | 23,104 KB |
最終ジャッジ日時 | 2023-09-05 14:10:23 |
合計ジャッジ時間 | 10,827 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 2 ms
4,380 KB |
testcase_02 | AC | 388 ms
9,568 KB |
testcase_03 | AC | 448 ms
10,500 KB |
testcase_04 | AC | 390 ms
9,700 KB |
testcase_05 | AC | 417 ms
12,280 KB |
testcase_06 | AC | 410 ms
12,280 KB |
testcase_07 | AC | 334 ms
10,884 KB |
testcase_08 | AC | 403 ms
12,212 KB |
testcase_09 | AC | 315 ms
10,444 KB |
testcase_10 | AC | 796 ms
23,104 KB |
testcase_11 | AC | 781 ms
22,836 KB |
testcase_12 | AC | 775 ms
23,032 KB |
testcase_13 | AC | 790 ms
22,984 KB |
testcase_14 | AC | 793 ms
23,100 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; template <typename T, typename F> class SegmentTree { F op; T e; int size; vector<T> data; void init(int n) { int log = 1; while (n > (1 << log)) ++log; size = 1 << log; data.assign(size << 1, e); } void update(int k) { k >>= 1; while (k > 0) { data[k] = op(data[k << 1], data[(k << 1) + 1]); k >>= 1; } } public: SegmentTree(int n, F op_, T e_) : op(op_), e(e_) { init(n); } SegmentTree(const vector<T> &v, F op_, T e_) : op(op_), e(e_) { int n = v.size(); init(n); for (int i = 0; i < n; i++) { data[i + size] = v[i]; } for (int i = size - 1; i > 0; --i) { data[i] = op(data[i << 1], data[(i << 1) + 1]); } } void set(int k, T v) { k += size; data[k] = v; update(k); } void add(int k, T v) { k += size; data[k] += v; update(k); } T get_all() { return data[1]; } T get_range(int l, int r) { T result_l = e, result_r = e; l += size; r += size; while (l < r) { if (l & 1) { result_l = op(result_l, data[l++]); } if (r & 1) { result_r = op(data[--r], result_r); } l >>= 1; r >>= 1; } return op(result_l, result_r); } T operator[](int k) { return data[k + size]; } }; void solve() { int q; cin >> q; vector<pair<int, int>> query; query.reserve(q); map<int, int> mp; int n = 0; for (int i = 0; i < q; i++) { int t, x = 0; cin >> t; if (t == 1 || t == 2) { cin >> x; if (mp.find(x) == mp.end()) { mp[x] = n++; } } query.emplace_back(t, x); } auto f = [](int x, int y) -> int { return x & y; }; int e = (1 << 30) - 1; SegmentTree<int, decltype(f)> seg(n, f, e); set<int> s; for (auto &[t, x]: query) { if (t == 1) { int i = mp[x]; seg.set(i, x); s.insert(x); } else if (t == 2) { int i = mp[x]; seg.set(i, e); s.erase(x); } else { if (s.size() == 0) { cout << -1 << '\n'; } else { cout << seg.get_all() << '\n'; } } } } int main() { int q = 1; // cin >> q; while (q--) { solve(); } }