結果
問題 | No.789 範囲の合計 |
ユーザー | AC2K |
提出日時 | 2023-05-04 12:41:14 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,787 bytes |
コンパイル時間 | 1,711 ms |
コンパイル使用メモリ | 115,996 KB |
実行使用メモリ | 18,552 KB |
最終ジャッジ日時 | 2024-05-01 22:38:05 |
合計ジャッジ時間 | 4,197 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
16,512 KB |
testcase_01 | AC | 3 ms
7,768 KB |
testcase_02 | TLE | - |
testcase_03 | -- | - |
testcase_04 | -- | - |
testcase_05 | -- | - |
testcase_06 | -- | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
コンパイルメッセージ
In member function 'S kyopro::segtree<S, op, e>::prod(int, int) [with S = int; S (* op)(S, S) = op; S (* e)() = e]', inlined from 'int main()' at main.cpp:93:28: main.cpp:52:20: warning: 'seg.kyopro::segtree<int, op, e>::n' may be used uninitialized [-Wmaybe-uninitialized] 52 | while (1) { | ~~~~~~~^ main.cpp: In function 'int main()': main.cpp:77:33: note: 'seg.kyopro::segtree<int, op, e>::n' was declared here 77 | lg++; | ^
ソースコード
#line 2 "main.cpp" #include <cassert> #include <memory> #line 2 "src/data-structure/hash_map.hpp" #include <bits/stl_algobase.h> #include <chrono> namespace kyopro { /// @brief HashMap template <typename Key, typename Val, uint32_t n = 1 << 20, Val default_val = Val()> class hash_map { using u32 = uint32_t; using u64 = uint64_t; u64* flag = new u64[n]; Key* keys = new Key[n]; Val* vals = new Val[n]; static constexpr u32 shift = 64 - std::__lg(n); u64 r; u32 get_hash(const Key& k) const { return ((u64)k * r) >> shift; } static constexpr uint8_t mod_msk = (1 << 6) - 1; public: explicit constexpr hash_map() { r = std::chrono::steady_clock::now().time_since_epoch().count(); r ^= r >> 16; r ^= r << 32; } Val& operator[](const Key& k) { u32 hash = get_hash(k); while (1) { if (!(flag[hash >> 6] & (static_cast<u64>(1) << (hash & mod_msk)))) { keys[hash] = k; flag[hash >> 6] |= static_cast<u64>(1) << (hash & mod_msk); return vals[hash] = default_val; } if (keys[hash] == k) return vals[hash]; hash = (hash + 1) & (n - 1); } } Val* find(const Key& k) const { u32 hash = get_hash(k); while (1) { if (!(flag[hash >> 6] & (static_cast<u64>(1) << (hash & mod_msk)))) return nullptr; if (keys[hash] == k) return &(vals[hash]); hash = (hash + 1) & (n - 1); } } }; }; // namespace kyopro #line 5 "main.cpp" #include <vector> namespace kyopro { /// @brief Segment Tree template <class S, S (*op)(S, S), S (*e)()> class segtree { int lg, sz, n; hash_map<int, S, 1 << 20> dat; public: segtree() {} segtree(int n) : segtree() { sz = 1, lg = 0; while (sz <= n) { sz <<= 1; lg++; } } segtree(const std::vector<S>& vec) : n((int)vec.size()) { sz = 1, lg = 0; while (sz <= n) { sz <<= 1; lg++; } for (int i = 0; i < n; i++) { set(i, vec[i]); } build(); } void set(int p, const S& v) { dat[sz + p] = v; } void build() { for (int i = sz - 1; i > 0; i--) { dat[i] = op(dat[i << 1], dat[(i << 1) ^ 1]); } } S operator[](int p) { return dat[sz + p]; } void update(int p, const S& v) { p += sz; dat[p] = v; while (p >>= 1) { dat[p] = op(dat[(p << 1)], dat[(p << 1) ^ 1]); } } S prod(int l, int r) { if (l == 0 && r == n) { return dat[1]; } l += sz, r += sz; S sml = e(), smr = e(); while (l != r) { if (l & 1) sml = op(sml, dat[l++]); if (r & 1) smr = op(dat[--r], smr); l >>= 1, r >>= 1; } return op(sml, smr); } void apply(int p, const S& v) { update(p, op(dat[sz + p], v)); } }; }; // namespace kyopro /// @docs docs/data-structure/segtree.md /// @docs docs/data-structure/dynamic_segtree.md #include <iostream> inline int op(int x, int y) { return x + y; } inline int e() { return 0; } int main() { const size_t n = 1000000001; kyopro::segtree<int, op, e> seg(n); int q; std::cin >> q; long long ans = 0; while (q--) { int type; std::cin >> type; if (type == 0) { size_t x; long long y; std::cin >> x >> y; seg.apply(x, y); } else { size_t l, r; std::cin >> l >> r; ans += seg.prod(l, r + 1); } } std::cout << ans << '\n'; }