結果

問題 No.789 範囲の合計
ユーザー HaarHaar
提出日時 2020-02-09 05:14:04
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 120 ms / 1,000 ms
コード長 2,570 bytes
コンパイル時間 2,098 ms
コンパイル使用メモリ 204,544 KB
実行使用メモリ 34,816 KB
最終ジャッジ日時 2024-10-01 05:43:26
合計ジャッジ時間 3,931 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 1 ms
6,820 KB
testcase_02 AC 112 ms
28,928 KB
testcase_03 AC 37 ms
6,820 KB
testcase_04 AC 120 ms
32,128 KB
testcase_05 AC 93 ms
27,648 KB
testcase_06 AC 97 ms
28,928 KB
testcase_07 AC 33 ms
6,816 KB
testcase_08 AC 102 ms
34,816 KB
testcase_09 AC 91 ms
32,000 KB
testcase_10 AC 91 ms
20,224 KB
testcase_11 AC 74 ms
28,416 KB
testcase_12 AC 76 ms
28,544 KB
testcase_13 AC 2 ms
6,816 KB
testcase_14 AC 1 ms
6,820 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#ifdef DEBUG
#include <Mylib/Debug/debug.cpp>
#else
#define dump(...) ((void)0)
#endif


template <typename Monoid>
class DynamicSegmentTree{
  using value_type = typename Monoid::value_type;
  
  struct Node{
    value_type val;
    Node *left = nullptr, *right = nullptr;
    Node(const value_type &val): val(val) {}
  };
  
  const int64_t size;
  Node *root = nullptr;

  Node* update_aux(Node *node, int64_t l, int64_t r, int64_t pos, const value_type &val){
    if(r-l == 1){
      if(node) node->val = Monoid::op(node->val, val);
      else node = new Node(val);
    }else{
      int64_t m = (l+r)/2;
      if(!node) node = new Node(val);
      if(pos < m) node->left = update_aux(node->left, l, m, pos, val);
      else node->right = update_aux(node->right, m, r, pos, val);
      node->val = Monoid::op(node->left ? node->left->val : Monoid::id(), node->right ? node->right->val : Monoid::id());
    }
    return node;
  }

  value_type get_aux(Node* node, int64_t l, int64_t r, int64_t x, int64_t y) const {
    if(!node) return Monoid::id();
    if(x <= l && r <= y) return node ? node->val : Monoid::id();
    if(r < x || y < l) return Monoid::id();
    int64_t m = (l + r) >> 1;
    return Monoid::op(get_aux(node->left, l, m, x, y), get_aux(node->right, m, r, x, y));
  }

public:
  DynamicSegmentTree(int64_t n): size(pow(2,ceil(log2(n)))){ // [0,n)
    root = new Node(Monoid::id());
  }

  void update(int64_t i, const value_type &x){
    update_aux(root, 0, size, i, x);
  }

  value_type get(int64_t l, int64_t r) const {
    return get_aux(root, 0, size, l, r);
  }

  value_type operator[](int64_t i) const {
    return get(i, i+1);
  }
};



template <typename T, typename = void>
struct SumMonoid{
  using value_type = T;
  static value_type ZERO;
  constexpr inline static value_type id(){return ZERO;}
  constexpr inline static value_type op(const value_type &a, const value_type &b){return a + b;}
};

template <typename T>
struct SumMonoid<T, typename std::enable_if<std::is_arithmetic<T>::value>::type>{
  using value_type = T;
  constexpr inline static value_type id(){return 0;}
  constexpr inline static value_type op(const value_type &a, const value_type &b){return a + b;}
};







int main(){
  int n; scanf("%d", &n);

  DynamicSegmentTree<SumMonoid<int64_t>> seg(1000000001);

  int64_t ans = 0;
    
  for(int i = 0; i < n; ++i){
    int q,x,y; scanf("%d%d%d", &q, &x, &y);
    if(q == 0){
      seg.update(x,y);
    }else{
      ans += seg.get(x,y+1);
    }
  }

  printf("%lld\n", ans);
  
  return 0;
}
0