結果

問題 No.789 範囲の合計
ユーザー betrue12betrue12
提出日時 2019-02-08 22:37:21
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 178 ms / 1,000 ms
コード長 1,941 bytes
コンパイル時間 1,493 ms
コンパイル使用メモリ 172,248 KB
実行使用メモリ 50,352 KB
最終ジャッジ日時 2023-09-14 03:51:28
合計ジャッジ時間 3,930 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 167 ms
41,400 KB
testcase_03 AC 70 ms
4,380 KB
testcase_04 AC 178 ms
46,072 KB
testcase_05 AC 133 ms
39,596 KB
testcase_06 AC 137 ms
41,396 KB
testcase_07 AC 70 ms
4,380 KB
testcase_08 AC 149 ms
50,352 KB
testcase_09 AC 136 ms
46,016 KB
testcase_10 AC 139 ms
28,460 KB
testcase_11 AC 119 ms
40,660 KB
testcase_12 AC 117 ms
40,684 KB
testcase_13 AC 1 ms
4,376 KB
testcase_14 AC 1 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

template<typename T>
struct Segtree_ptr{
    int N;
    typedef function<T(T, T)> Func;
    Func f;
    T e;

    struct Node{
        int l, r;
        Node* ch[2];
        T val;
        Node(int l, int r, T val):l(l), r(r), val(val){ ch[0] = ch[1] = nullptr; }
    };

    Node* root;

    Segtree_ptr(){}
    Segtree_ptr(int Nin, Func fin, T ein){ initialize(Nin, fin, ein); }
    void initialize(int Nin, Func fin, T ein){
        f = fin; e = ein;
        N = 1;
        while(N < Nin) N <<= 1;
        root = new Node(0, N, e);
    }

    T getval(Node* node){ return (node ? node->val : e); }
    void recalculate(Node* node){ node->val = f(getval(node->ch[0]), getval(node->ch[1])); }

    void update(int k, T x){ update(root, k, x); }
    void update(Node* node, int k, T x){
        int l = node->l, r = node->r;
        if(k < l || r <= k) return;
        if(r-l == 1){
            node->val += x;
        }else{
            int d = (r-l)/2;
            int t = (k-l)/d;
            if(!node->ch[t]) node->ch[t] = new Node(l + t*d, l + (t+1)*d, e);
            update(node->ch[t], k, x);
            recalculate(node);
        }
    }

    // [a, b] inclusive
    T between(int a, int b){ return query(root, a, b+1); }

    T query(Node* node, int a, int b){
        if(!node) return e;
        int l = node->l, r = node->r;
        if(b <= l || r <= a) return e;
        if(a <= l && r <= b) return node->val;
        return f(query(node->ch[0], a, b), query(node->ch[1], a, b));
    }
};

int main(){
    int N;
    cin >> N;

    int MX = 1e9+2;
    Segtree_ptr<int64_t> st(MX, [](int64_t a, int64_t b){ return a+b; }, 0);
    int64_t ans = 0;

    while(N--){
        int q, x, y;
        scanf("%d %d %d", &q, &x, &y);
        if(q == 0){
            st.update(x, y);
        }else{
            ans += st.between(x, y);
        }
    }
    cout << ans << endl;
    return 0;
}
0