結果
問題 | No.789 範囲の合計 |
ユーザー | tonegawa |
提出日時 | 2021-04-01 21:01:06 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,044 bytes |
コンパイル時間 | 3,128 ms |
コンパイル使用メモリ | 147,456 KB |
実行使用メモリ | 13,888 KB |
最終ジャッジ日時 | 2024-06-01 02:39:31 |
合計ジャッジ時間 | 4,865 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
13,752 KB |
testcase_01 | AC | 2 ms
6,944 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 | -- | - |
ソースコード
#include <vector> #include <cassert> #include <algorithm> template<typename Idx = int, int bitlen = sizeof(Idx) * 8> struct pseudo_segment_tree{ Idx M, N; pseudo_segment_tree(Idx n):N(n){ M = 1; while(M < N) M <<= 1; } int depth(Idx k){ if(bitlen <= 32) return 31 - __builtin_clz(k + 1); return 63 - __builtin_clzll(k + 1); } Idx width(Idx k){ return M >> depth(k); } bool is_leaf(Idx k){ return width(k) == (Idx)1; } std::pair<Idx, Idx> index_to_range(Idx k){ assert(0 <= k && k < 2 * M - 1); int dep = depth(k); Idx offset = (k + 1) - ((Idx)1 << dep); Idx wid = M >> dep; return std::make_pair(offset * wid, (offset + 1) * wid); } std::vector<Idx> range_to_index(Idx l, Idx r){ l = std::max(l, 0), r = std::min(r, N); assert(l <= r); l += M, r += M; std::vector<Idx> left, right; while(l < r){ if(l & 1) left.push_back((l++) - 1); if(r & 1) right.push_back((--r) - 1); l >>= 1; r >>= 1; } std::reverse(right.begin(), right.end()); left.insert(left.end(), right.begin(), right.end()); return left; } std::vector<Idx> point_to_index(Idx k){ assert(0 <= k && k < N); k += M - 1; std::vector<Idx> ret{k}; while(k){ k = (k - 1) >> 1; ret.push_back(k); } return ret; } }; #include <iostream> #include <unordered_map> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using fast_map = gp_hash_table<int, long long>; int main(){ std::cin.tie(nullptr); std::ios::sync_with_stdio(false); int q;std::cin >> q; pseudo_segment_tree segment(1000000001); fast_map sum; long long ans = 0; for(int i=0;i<q;i++){ int t, a, b;std::cin >> t >> a >> b; if(t == 0){ auto indices = segment.point_to_index(a); for(auto idx : indices) sum[idx] += b; }else{ auto indices = segment.range_to_index(a, b + 1); for(auto idx : indices) ans += sum[idx]; } } std::cout << ans << '\n'; }