結果
問題 |
No.649 ここでちょっとQK!
|
ユーザー |
![]() |
提出日時 | 2025-02-11 06:10:43 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 517 ms / 3,000 ms |
コード長 | 4,422 bytes |
コンパイル時間 | 3,910 ms |
コンパイル使用メモリ | 282,404 KB |
実行使用メモリ | 152,940 KB |
最終ジャッジ日時 | 2025-02-11 06:10:56 |
合計ジャッジ時間 | 11,640 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 32 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #ifdef LOCAL #include <debug.hpp> #else #define debug(...) #endif // ref: https://nyaannyaan.github.io/library/data-structure/hash-map-variable-length.hpp template <typename Key, typename Val> struct HashMap { using u32 = uint32_t; using u64 = uint64_t; u32 cap, s; vector<Key> keys; vector<Val> vals; vector<bool> flag; u64 r; u32 shift; Val DefaultValue; static u64 rng() { u64 m = chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count(); m ^= m >> 16; m ^= m << 32; return m; } void reallocate() { cap <<= 1; vector<Key> k(cap); vector<Val> v(cap); vector<bool> f(cap); u32 sh = shift - 1; for (int i = 0; i < (int)flag.size(); i++) { if (flag[i]) { u32 hash = (u64(keys[i]) * r) >> sh; while (f[hash]) hash = (hash + 1) & (cap - 1); k[hash] = keys[i]; v[hash] = vals[i]; f[hash] = 1; } } keys.swap(k); vals.swap(v); flag.swap(f); --shift; } explicit HashMap() : cap(8), s(0), keys(cap), vals(cap), flag(cap), r(rng()), shift(64 - __lg(cap)), DefaultValue(Val()) {} Val& operator[](const Key& i) { u32 hash = (u64(i) * r) >> shift; while (true) { if (!flag[hash]) { if (s + s / 4 >= cap) { reallocate(); return (*this)[i]; } keys[hash] = i; flag[hash] = 1; ++s; return vals[hash] = DefaultValue; } if (keys[hash] == i) return vals[hash]; hash = (hash + 1) & (cap - 1); } } // exist -> return pointer of Val // not exist -> return nullptr const Val* find(const Key& i) const { u32 hash = (u64(i) * r) >> shift; while (true) { if (!flag[hash]) return nullptr; if (keys[hash] == i) return &(vals[hash]); hash = (hash + 1) & (cap - 1); } } // return vector< pair<const Key&, val& > > vector<pair<Key, Val>> enumerate() const { vector<pair<Key, Val>> ret; for (u32 i = 0; i < cap; ++i) if (flag[i]) ret.emplace_back(keys[i], vals[i]); return ret; } int size() const { return s; } // set default_value void set_default(const Val& val) { DefaultValue = val; } }; /** * @brief Hash Map(可変長版) * @docs docs/data-structure/hash-map.md */ template <class S, class T> struct DynamicBinaryIndexedTree { S N; HashMap<S, T> data; DynamicBinaryIndexedTree() = default; DynamicBinaryIndexedTree(S size) : N(size + 1) {} void add(S i, T x) { assert(0 <= i && i < N); for (++i; i <= N; i += i & -i) data[i] += x; } void imos(int l, int r, T x) { add(l, x), add(r, -x); } T sum(S i) const { if (i < 0) return T{}; T res{}; for (; i > 0; i -= i & -i) { // std::unordered_map の場合はこちら // auto p = data.find(i); // res += p != data.end() ? p->second : T{}; auto p = data.find(i); res += p ? *p : T{}; } return res; } T sum(S l, S r) const { return sum(r) - sum(l); } T operator[](S i) const { return sum(i + 1) - sum(i); } S lower_bound(T w) { if (w <= 0) return 0; S i = 0; for (S k = S(1) << __lg(N); k > 0; k >>= 1) { if (i + k <= N && data[i + k] < w) { w -= data[i + k]; i += k; } } return i + 1; } }; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); int Q, K; cin >> Q >> K; constexpr ll M = ll(1e18) + 1; DynamicBinaryIndexedTree<ll, int> bit(M); while (Q--) { int type; cin >> type; if (type == 1) { ll v; cin >> v; bit.add(v, 1); } if (type == 2) { ll pos = bit.lower_bound(K) - 1; cout << (pos < M ? pos : -1) << '\n'; if (pos < M) bit.add(pos, -1); } } }