結果

問題 No.789 範囲の合計
ユーザー HaarHaar
提出日時 2020-02-09 04:09:30
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 135 ms / 1,000 ms
コード長 2,677 bytes
コンパイル時間 2,462 ms
コンパイル使用メモリ 212,376 KB
実行使用メモリ 37,340 KB
最終ジャッジ日時 2024-10-01 05:40:42
合計ジャッジ時間 4,886 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,820 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 127 ms
30,940 KB
testcase_03 AC 43 ms
6,820 KB
testcase_04 AC 135 ms
34,268 KB
testcase_05 AC 109 ms
29,656 KB
testcase_06 AC 112 ms
30,956 KB
testcase_07 AC 40 ms
6,820 KB
testcase_08 AC 130 ms
37,340 KB
testcase_09 AC 125 ms
34,396 KB
testcase_10 AC 112 ms
21,380 KB
testcase_11 AC 93 ms
30,672 KB
testcase_12 AC 99 ms
30,672 KB
testcase_13 AC 2 ms
6,816 KB
testcase_14 AC 1 ms
6,816 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;
  
  class Node{
  public:
    value_type val;
    Node *left = nullptr, *right = nullptr;
    Node(const value_type &val): val(val) {}
  };
  
  const int64_t size;

  Node *root = nullptr;
  std::unordered_map<int64_t, Node*> umap;

  Node* _update(Node *node, int64_t l, int64_t r, int64_t pos, const value_type &val){
    int64_t m = (l+r)/2;
    if(r-l == 1){
      if(node) node->val = Monoid::op(node->val, val);
      else node = new Node(val);
      umap[pos] = node;
    }else{
      if(!node) node = new Node(val);
      if(pos<m) node->left = _update(node->left, l, m, pos, val);
      else node->right = _update(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 _query(Node* node, int64_t l, int64_t r, int64_t x, int64_t y){
    if(!node) return Monoid::id();
    int64_t m = (l+r)/2;
    if(x <= l && r <= y) return node ? node->val : Monoid::id();
    if(r < x || y < l) return Monoid::id();
    return Monoid::op(_query(node->left, l, m, x, y), _query(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(root, 0, size, i, x);
  }

  value_type get(int64_t x, int64_t y){
    return _query(root, 0, size, x, y);
  }

  value_type operator[](int64_t i) const{
    if(umap.find(i) != umap.end()) return umap[i]->val;
    else return Monoid::id();
  }
};



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