結果

問題 No.1000 Point Add and Array Add
ユーザー ir5ir5
提出日時 2024-06-21 16:02:22
言語 C++23(gcc13)
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 448 ms / 2,000 ms
コード長 6,891 bytes
コンパイル時間 2,091 ms
コンパイル使用メモリ 158,796 KB
実行使用メモリ 17,412 KB
最終ジャッジ日時 2024-06-21 16:02:31
合計ジャッジ時間 7,890 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 1 ms
6,944 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 1 ms
6,944 KB
testcase_07 AC 1 ms
6,940 KB
testcase_08 AC 1 ms
6,944 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 AC 2 ms
6,944 KB
testcase_12 AC 4 ms
6,940 KB
testcase_13 AC 3 ms
6,940 KB
testcase_14 AC 5 ms
6,944 KB
testcase_15 AC 4 ms
6,940 KB
testcase_16 AC 328 ms
14,188 KB
testcase_17 AC 260 ms
11,520 KB
testcase_18 AC 427 ms
17,412 KB
testcase_19 AC 448 ms
17,248 KB
testcase_20 AC 399 ms
17,348 KB
testcase_21 AC 410 ms
17,268 KB
testcase_22 AC 424 ms
17,276 KB
testcase_23 AC 413 ms
17,336 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <numeric>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <functional>
#include <iomanip>
using namespace std;
using ll = long long;

class range {private: struct I{int x;int operator*(){return x;}bool operator!=(I& lhs){return x<lhs.x;}void operator++(){++x;}};I i,n;
public:range(int n_):i({0}),n({n_}){}range(int i_,int n_):i({i_}),n({n_}){}I& begin(){return i;}I& end(){return n;}};

template<typename T, typename U> ostream& operator<<(ostream& os, const pair<T, U>& p){ return os << "{" << p.first << ", " << p.second << "}"; }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& obj) { os << "{"; for (const auto& e : obj) os << e << ", "; return os << "}"; }
template<typename T> ostream& operator<<(ostream& os, const set<T>& obj) { os << "set{"; for (const auto& e : obj) os << e << ", "; return os << "}"; }
template<typename T, typename U> ostream& operator<<(ostream& os, const map<T, U>& obj) { os << "map{"; for (const auto& e : obj) os << e << ", "; return os << "}"; }
template<typename T> void take(vector<T>& vec, int n) { vec.resize(n); for (int i = 0; i < n; ++i) cin >> vec[i]; }

#ifdef ONLINE_JUDGE
#define dump(expr) ;
#else
#define dump(expr) { cerr << "\033[33m#L" << __LINE__ << ": " << expr << "\033[39m" << endl; }
#endif

// range update, range query segment tree
// based on https://maspypy.com/segment-tree-%e3%81%ae%e3%81%8a%e5%8b%89%e5%bc%b72
template <typename X, typename A>
struct LazySegmentTree {
  int n;
  vector<X> xs;
  vector<A> as;

  function<X(X, X)> fun;  // (x @ y) fold function
  function<X(X, A)> op;   // (x ^ a) operator
  function<A(A, A)> comp; // (a $ b) composition
  X unit_x;
  A unit_a;

  // Requirements:
  //   (x @ y) @ z = x @ (y @ z)
  //   (x^a) @  (y^a) = (x @ y)^a
  //   (x^a)^b = x^(ab)
  //   (a $ b) $ c = a $ (b $ c)

  LazySegmentTree(
      int n_,
      function<X(X, X)> fun_,
      function<X(X, A)> op_,
      function<A(A, A)> comp_,
      X unit_x_,
      A unit_a_
  ) : n(n_), xs(2 * n, unit_x_), as(2 * n, unit_a_),
      fun(fun_), op(op_), comp(comp_), unit_x(unit_x_), unit_a(unit_a_) {}

  void build(vector<X> seq) {
    assert((int)seq.size() == n);
    for (int i : range(n)) xs[n + i] = seq[i];
    for (int i = n - 1; i >= 1; --i) xs[i] = fun(xs[i << 1], xs[(i << 1) | 1]);
  }

  void setval(int i, X x) {
    // xs[i] := x
    i += n;
    propagate_above(i);
    xs[i] = x;
    as[i] = unit_a;
    recalc_above(i);
  }

  X at(int i) {
    // returns xs[i]
    i += n;
    propagate_above(i);
    return eval_at(i);
  }

  X fold(int l, int r) {
    // xs[l] @ xs[l + 1] @ ... @ xs[r - 1]
    l += n;
    r += n;
    propagate_above(l / (l & -l));
    propagate_above(r / (r & -r) - 1);
    X vl = unit_x;
    X vr = unit_x;
    while (l < r) {
      if (l & 1) {
        vl = fun(vl, eval_at(l));
        l++;
      }
      if (r & 1) {
        r--;
        vr = fun(eval_at(r), vr);
      }
      l >>= 1;
      r >>= 1;
    }
    return fun(vl, vr);
  }

  void operate_range(int l, int r, A a) {
    // x[l    ] := x[l    ] ^ a
    // x[l + 1] := x[l + 1] ^ a
    // ...
    // x[r - 1] := x[l - 1] ^ a
    l += n;
    r += n;
    propagate_above(l / (l & -l));
    propagate_above(r / (r & -r) - 1);
    while (l < r) {
      if (l & 1) {
        as[l] = comp(as[l], a);
        l++;
      }
      if (r & 1) {
        r--;
        as[r] = comp(as[r], a);
      }
      l >>= 1;
      r >>= 1;
    }
    recalc_above(l / (l & -l));
    recalc_above(r / (r & -r) - 1);
  }

  //---------------------------------------
  // auxiliary methods
  //---------------------------------------

  X eval_at(int i) {
    return op(xs[i], as[i]);
  }

  void propagate_at(int i) {
    xs[i] = eval_at(i);
    as[i << 1] = comp(as[i << 1], as[i]);
    as[(i << 1) | 1] = comp(as[(i << 1) | 1], as[i]);
    as[i] = unit_a;
  }

  void propagate_above(int i) {
    const int max_bitlen = 25;
    for (int h = max_bitlen; h >= 1; --h) {
      if (i >> h) propagate_at(i >> h);
    }
  }

  void recalc_above(int i) {
    while (i > 1) {
      i >>= 1;
      xs[i] = fun(eval_at(i << 1), eval_at((i << 1) | 1));
    }
  }
};

template <typename T>
LazySegmentTree<T, T> add_lazy_segment_tree_factory(int n) {
  return LazySegmentTree<T, T>(
      n,
      [](ll x, ll y) -> T { return x + y; },
      [](ll x, ll a) -> T { return x + a; },
      [](ll a, ll b) -> T { return a + b; },
      (T)0,
      (T)0
  );
}

namespace solver {

template<typename T1, typename T2> struct In2 {
  T1 a; T2 b;
  friend std::istream& operator>>(std::istream& is, In2& obj) { T1 t1; T2 t2; is >> t1 >> t2; obj = {t1, t2}; return is; }
};

template<typename T1, typename T2, typename T3> struct In3 {
  T1 a; T2 b; T3 c;
  friend std::istream& operator>>(std::istream& is, In3& obj) { T1 t1; T2 t2; T3 t3; is >> t1 >> t2 >> t3; obj = {t1, t2, t3}; return is; }
};

ll n, q;
vector<ll> vs;
vector<In3<char, ll, ll>> vq;

void read() {
  cin >> n >> q;
  take(vs, n);
  take(vq, q);
}

using RetType = void;

RetType run0() {
  using Pll = pair<ll, ll>;
  LazySegmentTree<Pll, ll> seg(
      n,
      [](Pll, Pll) -> Pll { return {0, 0}; },
      [](Pll p, ll a) -> Pll { return {p.first, a * p.first + p.second}; },
      [](ll a, ll b) -> char { return a + b; },
      Pll(0, 0),
      0
  );

  vector<Pll> init(n);
  for (int i : range(n)) init[i].first = vs[i];
  seg.build(init);

  for (auto query : vq) {
    if (query.a == 'A') {
      // add
      ll i = query.b - 1;
      Pll p = seg.at(i);
      p.first += query.c;
      seg.setval(i, p);
    }
    else {
      // act
      ll i = query.b - 1;
      ll j = query.c - 1;
      seg.operate_range(i, j + 1, 1);
    }

    // dump(seg.xs);
    // dump(seg.as);
  }

  for (int i : range(n)) cout << seg.at(i).second << " ";
  cout << endl;
}

RetType run() {
  auto seg = add_lazy_segment_tree_factory<ll>(n);

  vector<ll> bs(n);
  for (int k = q - 1; k >= 0; --k) {
    auto query = vq[k];
    if (query.a == 'A') {
      int i = query.b - 1;
      ll count = seg.fold(i, i + 1);
      bs[i] += count * query.c;
    }
    else {
      ll i = query.b - 1;
      ll j = query.c - 1;
      seg.operate_range(i, j + 1, 1);
    }
  }

  for (int i : range(n)) {
    ll count = seg.fold(i, i + 1);
    bs[i] += count * vs[i];
  }

  dump(bs);

  for (ll b : bs) cout << b << " ";
  cout << endl;
}

}  // namespace

template <typename F>
void run(F f) { if constexpr (std::is_same_v<decltype(f()), void>) f(); else cout << f() << endl; }

int main(int argc, char** argv) {
  cerr << fixed << setprecision(12);
  cout << fixed << setprecision(12);
  int testcase = 1;
  if (argc > 1) testcase = atoi(argv[1]);
  while (testcase--) {
    solver::read();
  }
  run(solver::run);
}
0