結果
問題 | No.789 範囲の合計 |
ユーザー | tonegawa |
提出日時 | 2023-05-01 14:27:57 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 70 ms / 1,000 ms |
コード長 | 4,824 bytes |
コンパイル時間 | 939 ms |
コンパイル使用メモリ | 81,308 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-04-30 16:49:19 |
合計ジャッジ時間 | 2,781 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 67 ms
6,940 KB |
testcase_03 | AC | 44 ms
6,944 KB |
testcase_04 | AC | 70 ms
6,940 KB |
testcase_05 | AC | 52 ms
6,944 KB |
testcase_06 | AC | 55 ms
6,944 KB |
testcase_07 | AC | 34 ms
6,944 KB |
testcase_08 | AC | 47 ms
6,944 KB |
testcase_09 | AC | 44 ms
6,944 KB |
testcase_10 | AC | 68 ms
6,944 KB |
testcase_11 | AC | 46 ms
6,944 KB |
testcase_12 | AC | 45 ms
6,940 KB |
testcase_13 | AC | 2 ms
6,940 KB |
testcase_14 | AC | 2 ms
6,944 KB |
ソースコード
#include <vector> #include <cassert> #include <limits> template<typename monoid, typename Val> struct sparse_segment_tree{ private: struct node{ int idx; node *l, *r; Val val, sum; node(int idx, Val val): idx(idx), l(nullptr), r(nullptr), val(val), sum(val){} }; node *make_node(int idx, Val val = monoid::template id<Val>()){ return new node(idx, val); } void 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); } void set(node* &v, int k, Val x, int l, int r){ if(!v){ v = make_node(k, x); return; } if(v->idx == k){ v->val = x; eval(v); return; } int 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); } Val get(node *v, int k, int l, int r){ if(!v) return monoid::template id<Val>(); if(v->idx == k) return v->val; int mid = ((long long)l + r) >> 1; if(k < mid) return get(v->l, k, l, mid); else return get(v->r, k, mid, r); } void update(node* &v, int k, Val x, int l, int r){ if(!v){ v = make_node(k, x); return; } if(v->idx == k){ v->val = monoid::template merge<Val>(v->val, x); eval(v); return; } int 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); } Val query(node *v, int a, int b, int l, int r){ if(!v || b <= l || r <= a) return monoid::template id<Val>(); if(a <= l && r <= b) return v->sum; int 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> std::pair<int, Val> bisect_from_left(node *v, const int l, const F &f, Val ok){ if(v->rx <= l) return {-1, ok}; if(l <= v->lx){ Val m = monoid::template merge<Val>(ok, v->sum); if(!f(m)) return {-1, m}; if(v->rx - v->lx == 1) return {v->lx, m}; } std::pair<int, Val> x{-1, monoid::template id<Val>()}; if(v->l) x = bisect_from_left(v->l, l, f, ok); if(x.first != -1) return x; if(v->r) x = bisect_from_left(v->r, l, f, ok); return x; } template<typename F> std::pair<int, Val> bisect_from_right(node *v, const int r, const F &f, Val ok){ if(r < v->lx) return {-1, ok}; if(v->rx <= r + 1){ Val m = monoid::template merge<Val>(v->sum, ok); if(!f(m)) return {-1, m}; if(v->rx - v->lx == 1) return {v->lx, m}; } std::pair<int, Val> x{-1, monoid::template id<Val>()}; if(v->r) x = bisect_from_right(v->r, r, f, ok); if(x.first != -1) return x; if(v->l) x = bisect_from_right(v->l, r, f, ok); return x; } node *root; int minx, maxx; public: sparse_segment_tree(): root(nullptr), minx(0), maxx(0){} sparse_segment_tree(int minx, int maxx): root(nullptr), minx(minx), maxx(maxx){} void set(int k, Val x){ set(root, k, x, minx, maxx); } Val get(int k){ return get(root, k, minx, maxx); } void update(int k, Val x){ update(root, k, x, minx, maxx); } Val query(int l, int r){ return query(root, l, r, minx, maxx); } // f(sum[l, r])がtrueになる最左のr. ない場合は-1 template<typename F> int bisect_from_left(int l, const F &f){ assert(!f(monoid::template id<Val>())); return bisect_from_left(root, l, f, monoid::template id<Val>()).first; } // f(sum[l, r])がtrueになる最右のl. ない場合は-1 template<typename F> int bisect_from_right(int r, const F &f){ assert(!f(monoid::template id<Val>())); return bisect_from_right(root, r, f, monoid::template id<Val>()).first; } }; 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; sparse_segment_tree<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.update(b, c); }else{ ans += seg.query(b, c + 1); } } std::cout << ans << '\n'; }