結果

問題 No.789 範囲の合計
ユーザー ikeyanabcd894ikeyanabcd894
提出日時 2019-06-01 17:31:28
言語 C++11
(gcc 13.3.0)
結果
RE  
実行時間 -
コード長 1,055 bytes
コンパイル時間 1,364 ms
コンパイル使用メモリ 163,596 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-09-17 19:57:03
合計ジャッジ時間 3,836 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 RE * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
struct SegmentTree{
  private:
  int n; vector<int> node;
  public:
  SegmentTree(vector<int> v){
    int sz=(int)v.size();
    n=1; while(n<sz)n*=2;
    node.resize(2*n-1,0);
    for(int i=0;i<sz;i++)node[i+n-1]=v[i];
    for(int i=n-2;i>=0;i--)node[i]=node[2*i+1]+node[2*i+2];
  }
  void add(int k,int val){
    k+=n-1;
    node[k]+=val;
    while(k > 0) {
            k = (k - 1) / 2;
            node[k] = node[2*k+1] + node[2*k+2];
        }
    }
 
    int getsum(int a, int b, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        if(b <= l || r <= a) return 0;
        if(a <= l && r <= b) return node[k];
 
        int vl = getsum(a, b, 2*k+1, l, (l+r)/2);
        int vr = getsum(a, b, 2*k+2, (l+r)/2, r);
        return vl + vr;
    }
};
 
int main() {
  int n;
  cin >> n;
  long long ans=0;
  SegmentTree seg(vector<int>(n,0));
  for(int i=0;i<n;i++){
    int q,s,t; cin >> q >> s >> t;
    if(q==0){seg.add(s,t);}
    else{ans+=(long long)seg.getsum(s,t+1);}
  }
  cout << ans << endl;
}
0