結果
問題 | No.789 範囲の合計 |
ユーザー | tonegawa |
提出日時 | 2023-05-01 16:25:15 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 114 ms / 1,000 ms |
コード長 | 5,884 bytes |
コンパイル時間 | 780 ms |
コンパイル使用メモリ | 77,308 KB |
実行使用メモリ | 70,272 KB |
最終ジャッジ日時 | 2024-04-30 17:34:40 |
合計ジャッジ時間 | 2,754 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 104 ms
40,448 KB |
testcase_03 | AC | 114 ms
70,272 KB |
testcase_04 | AC | 108 ms
46,208 KB |
testcase_05 | AC | 83 ms
38,400 KB |
testcase_06 | AC | 89 ms
40,576 KB |
testcase_07 | AC | 95 ms
62,720 KB |
testcase_08 | AC | 97 ms
51,456 KB |
testcase_09 | AC | 86 ms
46,080 KB |
testcase_10 | AC | 86 ms
25,856 KB |
testcase_11 | AC | 91 ms
51,200 KB |
testcase_12 | AC | 91 ms
51,200 KB |
testcase_13 | AC | 2 ms
6,944 KB |
testcase_14 | AC | 2 ms
6,940 KB |
ソースコード
#include <vector> #include <numeric> #include <limits> #include <cassert> template<typename monoid, typename Val> struct persistent_segment_tree_iter; template<typename monoid, typename Val, typename I> struct persistent_segment_tree{ private: using node = persistent_segment_tree<monoid, Val, I>; I idx; node *l, *r; Val val, sum; persistent_segment_tree(){} persistent_segment_tree(I idx, Val val): idx(idx), l(nullptr), r(nullptr), val(val), sum(val){} static node *make_node(I idx, Val x = monoid::template id<Val>()){ return new node(idx, x); } static node *copy_node(node *v){ assert(v); return new node(*v); } static node *eval(node *v){ v->sum = v->val; if(v->l) v->sum = monoid::template merge<Val>(v->l->sum, v->sum); if(v->r) v->sum = monoid::template merge<Val>(v->sum, v->r->sum); return v; } static void set(node* &v, int k, Val x, I l, I r){ if(!v){ v = make_node(k, x); return; } v = copy_node(v); if(v->idx == k){ v->val = x; eval(v); return; } I mid = ((long long)l + r) >> 1; if(k < mid){ if(v->idx < k) std::swap(v->idx, k), std::swap(v->val, x); set(v->l, k, x, l, mid); }else{ if(v->idx > k) std::swap(v->idx, k), std::swap(v->val, x); set(v->r, k, x, mid, r); } eval(v); } static void update(node* &v, int k, Val x, I l, I r){ if(!v){ v = make_node(k, x); return; } v = copy_node(v); if(v->idx == k){ v->val = monoid::template merge<Val>(v->val, x); eval(v); return; } I mid = ((long long)l + r) >> 1; if(k < mid){ if(v->idx < k) std::swap(v->idx, k), std::swap(v->val, x); update(v->l, k, x, l, mid); }else{ if(v->idx > k) std::swap(v->idx, k), std::swap(v->val, x); update(v->r, k, x, mid, r); } eval(v); } static Val get(node *v, int k, I l, I r){ if(!v) return monoid::template id<Val>(); if(v->idx == k) return v->val; I mid = ((long long)l + r) >> 1; if(k < mid) return get(v->l, k, l, mid); else return get(v->r, k, mid, r); } static Val query(node *v, I a, I b, I l, I r){ if(!v || b <= l || r <= a) return monoid::template id<Val>(); if(a <= l && r <= b) return v->sum; I mid = ((long long)l + r) >> 1; Val ret = query(v->l, a, b, l, mid); if(a <= v->idx && v->idx < b) ret = monoid::template merge<Val>(ret, v->val); return monoid::template merge<Val>(ret, query(v->r, a, b, mid, r)); } template<typename F> static I bisect_from_left(node *v, const I k, const F &f, I l, I r, Val &ok, const I maxx){ if(!v || r <= k) return maxx; Val m = monoid::template merge<Val>(ok, v->sum); if(k <= l && !f(m)){ ok = m; return maxx; } I mid = ((long long)l + r) >> 1; I x = bisect_from_left(v->l, k, f, l, mid, ok, maxx); if(x != maxx) return x; if(k <= v->idx){ ok = monoid::template merge<Val>(ok, v->val); if(f(ok)) return v->idx; } return bisect_from_left(v->r, k, f, mid, r, ok, maxx); } template<typename F> static I bisect_from_right(node *v, const I k, const F &f, I l, I r, Val ok, const I maxx){ if(!v || k < l) return maxx; Val m = monoid::template merge<Val>(v->sum, ok); if(r <= k + 1 && !f(m)){ ok = m; return maxx; } I mid = ((long long)l + r) >> 1; I x = bisect_from_right(v->r, k, f, mid, r, ok, maxx); if(x != maxx) return x; if(v->idx <= k){ ok = monoid::template merge<Val>(v->val, ok); if(f(ok)) return v->idx; } return bisect_from_right(v->l, k, f, l, mid, ok, maxx); } friend persistent_segment_tree_iter<monoid, Val>; }; template<typename monoid, typename Val> struct persistent_segment_tree_iter{ private: using I = int; using node = persistent_segment_tree<monoid, Val, I>; using iter = persistent_segment_tree_iter<monoid, Val>; I minx, maxx; node *root; persistent_segment_tree_iter(I minx, I maxx, node *v): minx(minx), maxx(maxx), root(v){} public: persistent_segment_tree_iter(I minx, I maxx): minx(minx), maxx(maxx), root(nullptr){} iter set(I k, Val x){ assert(minx <= k && k < maxx); node *r = root; node::set(r, k, x, minx, maxx); return iter(minx, maxx, r); } iter update(int k, Val x){ assert(minx <= k && k < maxx); node *r = root; node::update(r, k, x, minx, maxx); return iter(minx, maxx, r); } Val get(I k){ assert(minx <= k && k < maxx); return node::get(root, k, minx, maxx); } Val query(I l, I r){ assert(minx <= l && r <= maxx); return node::query(root, l, r, minx, maxx); } // f(sum[l, r])がtrueになる最左のr. ない場合はmaxx template<typename F> int bisect_from_left(I l, const F &f){ assert(minx <= l && l < maxx); Val x = monoid::template id<Val>(); return node::bisect_from_left(root, l, f, minx, maxx, x, maxx); } // f(sum[l, r])がtrueになる最右のl. ない場合はmaxx template<typename F> int bisect_from_right(int r, const F &f){ assert(minx <= r && r < maxx); Val x = monoid::template id<Val>(); return node::bisect_from_right(root, r, f, minx, maxx, x, maxx); } }; struct point_add_range_sum{ template<typename T> static T id(){ return 0; } template<typename T> static T update(T a, T b){ return a + b; } template<typename T> static T merge(T a, T b){ return a + b; } }; #include <iostream> int main(){ std::cin.tie(nullptr); std::ios::sync_with_stdio(false); int n; std::cin >> n; persistent_segment_tree_iter<point_add_range_sum, int> seg(0, 1000000001); long long ans = 0; for(int i = 0; i < n; i++){ int a, b, c; std::cin >> a >> b >> c; if(!a){ seg = seg.update(b, c); }else{ ans += seg.query(b, c + 1); } } std::cout << ans << '\n'; }