結果

問題 No.789 範囲の合計
ユーザー Imperi_NightImperi_Night
提出日時 2023-11-18 00:58:31
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,788 bytes
コンパイル時間 1,343 ms
コンパイル使用メモリ 102,664 KB
実行使用メモリ 41,960 KB
最終ジャッジ日時 2023-11-18 00:58:35
合計ジャッジ時間 3,752 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 TLE -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
権限があれば一括ダウンロードができます

ソースコード

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;
  static node pool[MAX_SIZE];
  DynamicSegTree(u64 _n) : n(_n), root(0) {}

  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); }
};
template <class T, T op(T, T), T e()>
DynamicSegTree<T, op, e>::node DynamicSegTree<T, op, e>::pool[MAX_SIZE];

using namespace std;

using i64 = long long;

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

i64 e() { return 0; }

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