結果

問題 No.789 範囲の合計
ユーザー niuezniuez
提出日時 2019-08-11 16:43:16
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 220 ms / 1,000 ms
コード長 1,672 bytes
コンパイル時間 2,329 ms
コンパイル使用メモリ 168,216 KB
実行使用メモリ 34,684 KB
最終ジャッジ日時 2023-10-11 21:16:05
合計ジャッジ時間 5,307 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,368 KB
testcase_01 AC 1 ms
4,368 KB
testcase_02 AC 205 ms
28,548 KB
testcase_03 AC 80 ms
4,372 KB
testcase_04 AC 220 ms
31,852 KB
testcase_05 AC 174 ms
27,524 KB
testcase_06 AC 182 ms
28,584 KB
testcase_07 AC 72 ms
4,368 KB
testcase_08 AC 187 ms
34,684 KB
testcase_09 AC 173 ms
31,652 KB
testcase_10 AC 184 ms
20,120 KB
testcase_11 AC 146 ms
28,116 KB
testcase_12 AC 150 ms
28,096 KB
testcase_13 AC 1 ms
4,368 KB
testcase_14 AC 2 ms
4,368 KB
権限があれば一括ダウンロードができます

ソースコード

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