結果

問題 No.789 範囲の合計
コンテスト
ユーザー niuez
提出日時 2019-08-11 16:43:16
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 210 ms / 1,000 ms
コード長 1,672 bytes
コンパイル時間 1,824 ms
コンパイル使用メモリ 172,872 KB
実行使用メモリ 34,688 KB
最終ジャッジ日時 2024-09-13 20:08:26
合計ジャッジ時間 4,589 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

struct dynamic_segment_tree {
  using T = i64;
  T ide() { return 0ll; }
  T ope(const T& a, const T& b) { return a + b; }

  struct node {
    node* left;
    node* right;
    T val;
    node(T v): val(v), left(nullptr), right(nullptr) {}
  };

  i64 n;
  node* root;
  dynamic_segment_tree(const i64 sz): root(new node(ide())) {
    n = 1;
    while(n < sz) n *= 2;
  }
  T value(node* n) {
    if(n) return n->val;
    else return ide();
  }
  void update(node* n, i64 i, T x, i64 l, i64 r) {
    if(l + 1 == r) {
      n->val = x;
    }
    else {
      i64 m = (l + r) / 2;
      if(i < m) {
        if(!n->left) {
          n->left = new node(ide());
        }
        update(n->left, i, x, l, m);
      }
      else {
        if(!n->right) {
          n->right = new node(ide());
        }
        update(n->right, i, x, m, r);
      }
      n->val = ope(value(n->left), value(n->right));
    }
  }

  T get(node* n, i64 a, i64 b, i64 l, i64 r) {
    if(!n) return ide();
    if(a <= l && r <= b) return value(n);
    else if(r <= a || b <= l) return ide();
    else return ope(get(n->left, a, b, l, (l + r) / 2), get(n->right, a, b, (l + r) / 2, r));
  }

  void update(i64 i, T x) {
    update(root, i, x, 0, n);
  }

  T get(i64 a, i64 b) {
    return get(root, a, b, 0, n);
  }
};

int main() {
  dynamic_segment_tree seg(1000000000 + 10);
  i64 q;
  cin >> q;
  i64 ans = 0;
  for(int i = 0;i < q;i++) {
    i64 a, b, c;
    cin >> a >> b >> c;
    if(a == 0) {
      seg.update(b, seg.get(b, b + 1) + c);
    }
    else {
      ans += seg.get(b, c + 1);
    }
  }
  cout << ans << endl;
}
0