結果

問題 No.789 範囲の合計
コンテスト
ユーザー betrue12
提出日時 2019-02-08 22:37:21
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 195 ms / 1,000 ms
コード長 1,941 bytes
コンパイル時間 1,704 ms
コンパイル使用メモリ 174,108 KB
実行使用メモリ 50,432 KB
最終ジャッジ日時 2024-07-01 11:39:26
合計ジャッジ時間 4,416 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

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