結果

問題 No.789 範囲の合計
ユーザー ikeyanabcd894ikeyanabcd894
提出日時 2019-06-01 17:29:33
言語 C++11
(gcc 11.4.0)
結果
RE  
実行時間 -
コード長 1,102 bytes
コンパイル時間 1,458 ms
コンパイル使用メモリ 165,872 KB
実行使用メモリ 6,124 KB
最終ジャッジ日時 2023-10-17 22:47:13
合計ジャッジ時間 5,980 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 AC 2 ms
4,348 KB
testcase_02 RE -
testcase_03 AC 71 ms
6,112 KB
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 AC 64 ms
6,112 KB
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 AC 2 ms
4,348 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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