結果
問題 | No.789 範囲の合計 |
ユーザー | tonegawa |
提出日時 | 2023-05-16 05:50:12 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 160 ms / 1,000 ms |
コード長 | 2,580 bytes |
コンパイル時間 | 811 ms |
コンパイル使用メモリ | 81,072 KB |
実行使用メモリ | 50,688 KB |
最終ジャッジ日時 | 2024-05-08 06:59:14 |
合計ジャッジ時間 | 3,374 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 148 ms
40,576 KB |
testcase_03 | AC | 43 ms
5,376 KB |
testcase_04 | AC | 160 ms
45,440 KB |
testcase_05 | AC | 111 ms
38,912 KB |
testcase_06 | AC | 115 ms
40,704 KB |
testcase_07 | AC | 38 ms
5,376 KB |
testcase_08 | AC | 131 ms
49,536 KB |
testcase_09 | AC | 115 ms
45,312 KB |
testcase_10 | AC | 117 ms
28,032 KB |
testcase_11 | AC | 108 ms
50,688 KB |
testcase_12 | AC | 101 ms
50,688 KB |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
コンパイルメッセージ
main.cpp:1:9: warning: #pragma once in main file 1 | #pragma once | ^~~~
ソースコード
#pragma once #include <vector> #include <cassert> #include <algorithm> #include <iostream> template<typename Val> struct sparse_binary_indexed_tree{ private: using I = int; static constexpr int bitlen = sizeof(I) * 8; // idxの2進数においてk-bitから下位bitに向けて1がいくつ続くか static int count_consecutive_one(I idx, int k){ static_assert(bitlen == 32 || bitlen == 64); if(bitlen == 32) return __builtin_clz(~((uint32_t)idx << (31 - k))); return __builtin_clzll(~((uint64_t)idx << (63 - k))); } static int count_trailing_one(I idx){ static_assert(bitlen == 32 || bitlen == 64); if(bitlen == 32) return __builtin_ctz(~(uint32_t)idx); return __builtin_ctzll(~(uint64_t)idx); } I maxn; int h; struct node{ I idx; std::vector<node*> ch; Val val, sum; node(I idx, Val val): idx(idx), val(val), sum(val){} }; node *root; void update(node* &v, I idx, Val x, int h_cur){ if(!v) v = new node(idx, x); else v->sum += x; if(h_cur == -1 || count_trailing_one(idx) == h_cur + 1) return; // 残りの下位bitが全て1なら終了 int k = count_consecutive_one(idx, h_cur); if(v->ch.size() <= k) v->ch.resize(k + 1, nullptr); update(v->ch[k], idx, x, h_cur - 1 - k); } Val query(node *v, I idx, int h_cur){ if(!v || h_cur == -1) return Val(0); Val res = Val(0); int k = count_consecutive_one(idx, h_cur); int maxk = std::min(k, (int)v->ch.size()); for(int i = 0; i < maxk; i++) if(v->ch[i]) res += v->ch[i]->sum; if(v->ch.size() > k) res += query(v->ch[k], idx, h_cur - 1 - k); return res; } public: sparse_binary_indexed_tree(): root(nullptr){} // [0, n) sparse_binary_indexed_tree(I n): root(nullptr){ n = std::max(n + 1, 2); maxn = 1, h = 0; while(maxn < n) maxn <<= 1, h++; } void update(I idx, Val x){ assert(0 <= idx && idx < maxn); update(root, idx, x, h - 1); } Val query(I r){ assert(0 <= r && r <= maxn); return query(root, r, h - 1); } Val query(I l, I r){ assert(0 <= l && l <= r && r <= maxn); if(l == r) return Val(0); return query(root, r, h - 1) - query(root, l, h - 1); } }; #include <iostream> int main(){ std::cin.tie(nullptr); std::ios::sync_with_stdio(false); int n; std::cin >> n; sparse_binary_indexed_tree<long long> t(1000000001); long long ans = 0; for(int i = 0; i < n; i++){ int a, b, c; std::cin >> a >> b >> c; if(!a){ t.update(b, c); }else{ ans += t.query(b, c + 1); } } std::cout << ans << '\n'; }