結果
問題 |
No.3265 地元に帰れば天才扱い!
|
ユーザー |
![]() |
提出日時 | 2025-09-06 15:01:13 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,457 ms / 2,500 ms |
コード長 | 1,794 bytes |
コンパイル時間 | 6,650 ms |
コンパイル使用メモリ | 332,312 KB |
実行使用メモリ | 19,856 KB |
最終ジャッジ日時 | 2025-09-06 15:02:29 |
合計ジャッジ時間 | 40,526 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; long long op (long long a, long long b) { return a + b; } long long e () { return 0; } long long mapping (long long a, long long b) { return a + b; } long long composition (long long a, long long b) { return a + b; } long long id () { return 0; } int main() { long long N, M; cin >> N >> M; vector<long long> A(N); vector<long long> L(N); vector<long long> R(N); for (long long i = 0; i < N; ++i) cin >> A[i] >> L[i] >> R[i]; for (long long i = 0; i < N; ++i) { L[i]--; R[i]--; } lazy_segtree<long long, op, e, long long, mapping, composition, id> seg(M); segtree<long long, op, e> seg2(M); for (long long i = 0; i < N; ++i) { seg.apply(L[i], R[i] + 1, 1); } long long ans = 0; for (long long i = 0; i < N; ++i) { ans += 1LL * (R[i] - L[i] + 1) * A[i]; ans -= 1LL * A[i] * seg.get(i); } for (long long i = 0; i < N; ++i) { seg2.set(i, A[i]); } vector<long long> H(N); for (long long i = 0; i < N; ++i) H[i] = i; long long Q; cin >> Q; for (;Q--;) { long long X, Y, U, V; cin >> X >> Y >> U >> V; X--; Y--; U--; V--; ans += 1LL * seg.prod(H[X], H[X] + 1) * A[X]; seg2.set(H[X], 0); ans -= 1LL * (R[X] - L[X] + 1) * A[X]; ans += seg2.prod(L[X], R[X] + 1); seg.apply(L[X], R[X] + 1, -1); L[X] = U; R[X] = V; H[X] = Y; seg.apply(L[X], R[X] + 1, 1); ans -= seg2.prod(L[X], R[X] + 1); ans += 1LL * (R[X] - L[X] + 1) * A[X]; seg2.set(H[X], A[X]); ans -= 1LL * seg.prod(H[X], H[X] + 1) * A[X]; cout << ans << endl; } }