結果

問題 No.789 範囲の合計
ユーザー polyomino_24polyomino_24
提出日時 2019-02-09 00:20:39
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 197 ms / 1,000 ms
コード長 3,468 bytes
コンパイル時間 1,281 ms
コンパイル使用メモリ 132,252 KB
実行使用メモリ 68,972 KB
最終ジャッジ日時 2023-09-14 04:01:22
合計ジャッジ時間 4,469 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 20 ms
65,844 KB
testcase_01 AC 20 ms
65,900 KB
testcase_02 AC 188 ms
68,412 KB
testcase_03 AC 95 ms
65,888 KB
testcase_04 AC 197 ms
68,684 KB
testcase_05 AC 162 ms
68,184 KB
testcase_06 AC 167 ms
68,340 KB
testcase_07 AC 88 ms
65,920 KB
testcase_08 AC 167 ms
68,972 KB
testcase_09 AC 157 ms
68,660 KB
testcase_10 AC 180 ms
67,508 KB
testcase_11 AC 137 ms
68,608 KB
testcase_12 AC 137 ms
68,604 KB
testcase_13 AC 20 ms
65,852 KB
testcase_14 AC 20 ms
65,852 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define show(x) cout << #x << " = " << (x) << endl;
using namespace std;
using ll = long long;
using pii = pair<int,int>;
template<typename T> class dynamic_segtree{
private:
    struct node {
        T val;
        node *par, *left, *right;
        node() : val(identity), par(nullptr), left(nullptr), right(nullptr){}
    };
    void opr1(T& arg1,T arg2){
        arg1 += arg2;
    }
    T opr2(T arg1,T arg2){
        return arg1+arg2;
    }
    int nw_size;
    static const int POOL_SIZE = 2000000;
    static const int MAX_SIZE = 1000000001;
    static node *root;
    static node pool[POOL_SIZE];
    static const T identity = (T)0;
    node *alloc(){
        assert(nw_size < POOL_SIZE);
        return (&pool[nw_size++]);
    }
public:
    dynamic_segtree() : nw_size(0){ root = alloc(); }
    void insert(int a, T x, node *k = root, int l = 0, int r = MAX_SIZE){
        k->val = opr2(k->val,x);
        if(r - l == 1){
            return;
        }
        if(a < (l + r) / 2){
            if(!(k->left)){
                k->left = alloc();
                k->left->par = k;
            }
            insert(a, x, k->left, l, (l+r)/2);
        }else{
            if(!(k->right)){
                k->right = alloc();
                k->right->par = k;
            }
            insert(a, x, k->right, (l+r)/2, r);
        }
    }
    void update(int a, T x, node *k = root, int l = 0, int r = MAX_SIZE){
        if(r - l == 1){
            opr1(k->val,x);
            while(k->par){
                k = k->par;
                k->val = identity;
                if(k->left){
                    k->val = opr2(k->val,k->left->val);
                }
                if(k->right){
                    k->val = opr2(k->val,k->right->val);
                }
            }
            return;
        }
        if(a < (l + r) / 2){
            update(a, x, k->left, l, (l+r)/2);
        }else{
            update(a, x, k->right, (l+r)/2, r);
        }
    }
    T query(int a, int b, node *k = root, int l=0, int r = MAX_SIZE){
        if(b <= l || r <= a){
            return identity;
        }
        if(a <= l && r <= b){
            return k->val;
        }
        T vl = identity,vr = identity;
        if(k->left){
            vl = query(a, b, k->left, l, (l+r)/2);
        }
        if(k->right){
            vr = query(a, b, k->right, (l+r)/2, r);
        }
        return opr2(vl, vr);
    }
};
template<typename T> class dynamic_segtree<T>::node* dynamic_segtree<T>::root;
template<typename T> class dynamic_segtree<T>::node dynamic_segtree<T>::pool[POOL_SIZE];
int main(){
    dynamic_segtree<ll> seg;
    int q;
    cin >> q;
    set<int>st;
    ll ans = 0;
    while(q--){
        int a,b,c;
        cin >> a >> b >> c;
        if(a){
            ans += seg.query(b,c+1);
        }else{
            if(st.count(b)){
                seg.update(b,c);
            }else{
                st.insert(b);
                seg.insert(b,c);
            }
        }
    }
    cout << ans << endl;
}
0