結果

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