結果

問題 No.789 範囲の合計
ユーザー Imperi_NightImperi_Night
提出日時 2023-11-18 00:25:24
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 147 ms / 1,000 ms
コード長 2,594 bytes
コンパイル時間 1,088 ms
コンパイル使用メモリ 81,880 KB
実行使用メモリ 35,072 KB
最終ジャッジ日時 2024-09-26 05:35:45
合計ジャッジ時間 3,146 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 12 ms
34,944 KB
testcase_01 AC 12 ms
34,944 KB
testcase_02 AC 141 ms
34,944 KB
testcase_03 AC 97 ms
35,072 KB
testcase_04 AC 139 ms
35,004 KB
testcase_05 AC 125 ms
34,816 KB
testcase_06 AC 126 ms
35,072 KB
testcase_07 AC 89 ms
35,072 KB
testcase_08 AC 124 ms
34,988 KB
testcase_09 AC 118 ms
35,072 KB
testcase_10 AC 147 ms
34,944 KB
testcase_11 AC 115 ms
35,040 KB
testcase_12 AC 115 ms
35,072 KB
testcase_13 AC 18 ms
35,032 KB
testcase_14 AC 17 ms
35,068 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <iostream>
#include <new>
#include <utility>
#include <vector>

const int MAX_SIZE = 1010101;

template <class T, T op(T, T), T e()> struct DynamicSegTree {
  using u64 = unsigned long long;

  struct node {
    int left, right;
    T prod;
    T val;
    u64 pos;
    node() : node(-1, e()) {}
    node(int p, T x) : left(0), right(0), prod(x), val(x), pos(p) {}
  };

  inline u64 index(int x) { return pool[x].pos; }

  int counter = 1;
  u64 n;
  int root;
  node pool[MAX_SIZE];
  // DynamicSegTree(u64 _n) : n(_n), root(0) {}
  DynamicSegTree() : root(0) {}

  void set_size(u64 _n) { n = _n; }

  void update(int t) {
    pool[t].prod =
        op(op(pool[pool[t].left].prod, pool[t].val), pool[pool[t].right].prod);
  }

  void _set(int &t, u64 p, T &x, u64 l, u64 r) {
    if (!t) {
      t = counter++;
      pool[t] = node(p, x);
      return;
    }
    if (index(t) == p) {
      pool[t].val = x;
    } else {
      u64 mid = (l + r) >> 1;
      if (p < mid) {
        if (index(t) < p) {
          std::swap(pool[t].pos, p);
          std::swap(pool[t].val, x);
        }
        _set(pool[t].left, p, x, l, mid);
      } else {
        if (index(t) > p) {
          std::swap(pool[t].pos, p);
          std::swap(pool[t].val, x);
        }
        _set(pool[t].right, p, x, mid, r);
      }
    }
    update(t);
    return;
  }

  T _get(int &t, u64 p, u64 l, u64 r) {
    if (!t)
      return e();
    if (index(t) == p)
      return pool[t].val;
    u64 mid = (l + r) >> 1;
    if (p < mid)
      return _get(pool[t].left, p, l, mid);
    else
      return _get(pool[t].right, p, mid, r);
  }

  T _prod(int &t, u64 L, u64 R, u64 l, u64 r) {
    if (!t || R <= l || r <= L)
      return e();
    if (L <= l && r <= R)
      return pool[t].prod;
    u64 mid = (l + r) >> 1;
    T res = _prod(pool[t].left, L, R, l, mid);
    if (L <= index(t) && index(t) < R)
      res = op(res, pool[t].val);
    return op(res, _prod(pool[t].right, L, R, mid, r));
  }

  void set(u64 p, T x) { _set(root, p, x, 0, n); }

  T get(u64 p) { return _get(root, p, 0, n); }

  T prod(u64 l, u64 r) { return _prod(root, l, r, 0, n); }
};

using namespace std;

using i64 = long long;

i64 op(i64 a, i64 b) { return a + b; }

i64 e() { return 0; }

DynamicSegTree<i64, op, e> seg;

int main() {
  int q;
  cin >> q;
  i64 n = 1e9;
  n += 100;
  seg.set_size(n);
  i64 ans = 0;
  while (q--) {
    int t;
    i64 l, r;
    cin >> t >> l >> r;
    if (t == 0)
      seg.set(l, seg.get(l) + r);
    else {
      ans += seg.prod(l, r + 1);
    }
  }
  cout << ans << "\n";
}
0