結果

問題 No.789 範囲の合計
コンテスト
ユーザー Haar
提出日時 2020-02-09 05:14:04
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 130 ms / 1,000 ms
コード長 2,570 bytes
コンパイル時間 2,068 ms
コンパイル使用メモリ 195,964 KB
最終ジャッジ日時 2025-01-08 23:17:31
ジャッジサーバーID
（参考情報） 		judge1 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:102:14: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 2 has type ‘int64_t’ {aka ‘long int’} [-Wformat=]
  102 |   printf("%lld\n", ans);
      |           ~~~^     ~~~
      |              |     |
      |              |     int64_t {aka long int}
      |              long long int
      |           %ld
main.cpp:87:15: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   87 |   int n; scanf("%d", &n);
      |          ~~~~~^~~~~~~~~~
main.cpp:94:21: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   94 |     int q,x,y; scanf("%d%d%d", &q, &x, &y);
      |                ~~~~~^~~~~~~~~~~~~~~~~~~~~~

ソースコード

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