結果

問題 No.3265 地元に帰れば天才扱い!
ユーザー のらら
提出日時 2025-08-08 00:35:02
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 952 bytes
コンパイル時間 3,417 ms
コンパイル使用メモリ 181,400 KB
実行使用メモリ 22,676 KB
最終ジャッジ日時 2025-09-06 12:30:55
合計ジャッジ時間 11,705 ms
ジャッジサーバーID
(参考情報)
judge4 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample WA * 1 RE * 3
other RE * 21
権限があれば一括ダウンロードができます

ソースコード

diff #

//遅延評価セグ木1本で解いてみる
#include <iostream>
#include <algorithm>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
ll N, Q, X, Y, L, R;
struct S {
  ll val;
  ll total;
  ll deg;
};
using F = ll;
S op(S x,S y){
  return S{x.val + y.val, x.total + y.total, max(x.deg, y.deg)};
}
S e() { return S{0LL, 0LL, 0LL}; }
S mapping(F f, S x) {
  return S{x.val, f * x.val + x.total, f + x.deg};
}
F composition(F f, F g) {
  return f + g;
}
F id() { return 0LL; }

int main(){
  cin >> N;
  vector<S> A(N);
  for(int i = 0; i < N; i++){
    ll a;
    cin >> a;
    A[i] = S{a, 0, 0};
  }
  lazy_segtree<S, op, e, F, mapping, composition, id> seg(A);
  cin >> Q;
  for(int q = 1; q <= Q; q++){
    cin >> X >> Y >> L >> R;
    X--; L--;
    auto [val, total, deg] = seg.get(X);
    seg.set(X, S{Y, Y * deg, deg});
    seg.apply(L, R, 1LL);
    cout << seg.prod(0, N).total << endl;
  }
  return 0;
}
0