結果
問題 |
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 |
ソースコード
//遅延評価セグ木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; }