結果

問題 No.789 範囲の合計
ユーザー risujirohrisujiroh
提出日時 2019-02-08 22:02:27
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 196 ms / 1,000 ms
コード長 3,536 bytes
コンパイル時間 1,618 ms
コンパイル使用メモリ 166,028 KB
実行使用メモリ 50,676 KB
最終ジャッジ日時 2023-09-11 04:44:31
合計ジャッジ時間 4,203 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 176 ms
41,632 KB
testcase_03 AC 60 ms
4,376 KB
testcase_04 AC 196 ms
46,208 KB
testcase_05 AC 134 ms
39,656 KB
testcase_06 AC 143 ms
41,608 KB
testcase_07 AC 57 ms
4,380 KB
testcase_08 AC 152 ms
50,676 KB
testcase_09 AC 131 ms
46,192 KB
testcase_10 AC 134 ms
28,584 KB
testcase_11 AC 110 ms
40,724 KB
testcase_12 AC 112 ms
40,620 KB
testcase_13 AC 2 ms
4,380 KB
testcase_14 AC 2 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using lint = long long int;
using ulint = unsigned long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T, class U> void assign(V<T>& v, int n, const U& a) { v.assign(n, a); }
template<class T, class... Args> void assign(V<T>& v, int n, const Args&... args) { v.resize(n); for (auto&& e : v) assign(e, args...); }


struct SumMonoid {
  using T = lint;
  static T op(const T& lhs, const T& rhs) { return lhs + rhs; }
  static constexpr T e() { return 0; }
};

template<class Monoid> struct AddMonoidAct {
  using T = lint;
  static void ap(const T& act, typename Monoid::T& val, int len) { val += act * len; }
  static void cp(const T& lhs, T& rhs) { rhs += lhs; }
  static constexpr T id() { return 0; }
  static bool is_id(const T& act) { return act == id(); }
};

template<class Monoid, class MonoidAct, class Int = int> struct SegmentTree {
  using M = Monoid;
  using MA = MonoidAct;
  using Tv = typename M::T;
  using Ta = typename MA::T;
  struct Node;
  using Tree = Node*;

  struct Node {
    Tv val = M::e();
    Ta act = MA::id();
    Tree cl, cr;
  };

  const Int n;

  SegmentTree(Int n) : n(n), tree(new Node()) {}

  Tv get(Int l, Int r) {
    l = max<Int>(l, 0), r = min<Int>(r, n);
    if (l >= r) return M::e();
    return get(l, r, tree, 0, n);
  }

  void set(Int l, Int r, const Ta& f) {
    l = max<Int>(l, 0), r = min<Int>(r, n);
    if (l >= r) return;
    set(l, r, f, tree, 0, n);
  }

  void set(Int i, const Tv& a) {
    assert(0 <= i and i < n);
    set(i, a, tree, 0, n);
  }

private:
  Tree tree;

  void push(Tree& t, Int tl, Int tm, Int tr) {
    if (MA::is_id(t->act)) return;
    if (!t->cl) t->cl = new Node();
    MA::ap(t->act, t->cl->val, tm - tl);
    MA::cp(t->act, t->cl->act);
    if (!t->cr) t->cr = new Node();
    MA::ap(t->act, t->cr->val, tr - tm);
    MA::cp(t->act, t->cr->act);
    t->act = MA::id();
  }

  Tv get(Int l, Int r, Tree t, Int tl, Int tr) {
    if (!t) return M::e();
    if (l <= tl and tr <= r) return t->val;
    Int tm = tl + tr >> 1;
    push(t, tl, tm, tr);
    Tv resl = l < tm ? get(l, r, t->cl, tl, tm) : M::e(),
       resr = tm < r ? get(l, r, t->cr, tm, tr) : M::e();
    return M::op(resl, resr);
  }

  void set(Int l, Int r, const Ta& f, Tree& t, Int tl, Int tr) {
    if (!t) t = new Node();
    if (l <= tl and tr <= r) {
      MA::ap(f, t->val, tr - tl);
      MA::cp(f, t->act);
      return;
    }
    Int tm = tl + tr >> 1;
    push(t, tl, tm, tr);
    if (l < tm) set(l, r, f, t->cl, tl, tm);
    if (tm < r) set(l, r, f, t->cr, tm, tr);
    t->val = M::op(t->cl ? t->cl->val : M::e(), t->cr ? t->cr->val : M::e());
  }

  void set(Int i, const Tv& a, Tree& t, Int tl, Int tr) {
    if (!t) t = new Node();
    if (tr - tl == 1) {
      t->val = a;
      return;
    }
    Int tm = tl + tr >> 1;
    push(t, tl, tm, tr);
    if (i < tm) set(i, a, t->cl, tl, tm);
    else set(i, a, t->cr, tm, tr);
    t->val = M::op(t->cl ? t->cl->val : M::e(), t->cr ? t->cr->val : M::e());
  }
};

using ST = SegmentTree< SumMonoid, AddMonoidAct<SumMonoid>, lint >;
int main() {
  cin.tie(nullptr); ios_base::sync_with_stdio(false);
  ST st(1e9 + 1);
  lint res = 0;
  int n; cin >> n;
  while (n--) {
    int type; cin >> type;
    if (type == 0) {
      int x, y; cin >> x >> y;
      st.set(x, x + 1, y);
    } else {
      int l, r; cin >> l >> r, ++r;
      res += st.get(l, r);
    }
  }
  cout << res << '\n';
}
0