結果
問題 |
No.3265 地元に帰れば天才扱い!
|
ユーザー |
![]() |
提出日時 | 2025-09-06 16:58:24 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,181 ms / 2,500 ms |
コード長 | 1,889 bytes |
コンパイル時間 | 6,315 ms |
コンパイル使用メモリ | 332,376 KB |
実行使用メモリ | 24,704 KB |
最終ジャッジ日時 | 2025-09-06 16:59:03 |
合計ジャッジ時間 | 35,103 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using i32 = int; using u32 = unsigned int; using i64 = long long; using u64 = unsigned long long; #define FAST_IO \ ios::sync_with_stdio(false); \ cin.tie(0); const i64 INF = 1001001001001001001; using Modint = atcoder::static_modint<998244353>; struct S{ long long value; int size; }; using F = long long; S op2(S a, S b){ return {a.value+b.value, a.size+b.size}; } S e2(){ return {0, 0}; } S mapping(F f, S x){ return {x.value + f*x.size, x.size}; } F composition(F f, F g){ return f+g; } F id(){ return 0; } i64 op1(i64 a, i64 b) { return a + b; } i64 e1() { return 0; } int main() { FAST_IO int N, M; cin >> N >> M; vector<i64> A(N); vector<int> L(N) , R(N); for (int i = 0; i < N; i++) { cin >> A[i] >> L[i] >> R[i]; L[i]--; } std::vector<S> v(M, {0, 1}); atcoder::segtree<i64, op1, e1> seg1(M); atcoder::lazy_segtree<S, op2, e2, F, mapping, composition, id> seg2(v); i64 sum = 0; vector<int> idx(N); iota(idx.begin(), idx.end(), 0); for (int i = 0; i < N; i++) { sum += A[i] * (R[i] - L[i]); seg1.set(i, A[i]); seg2.apply(L[i], R[i], 1); } for (int i = 0; i < N; i ++) { sum -= seg1.prod(L[i], R[i]); } int Q; cin >> Q; for (int i = 0; i < Q; i ++) { int x, y, u, v; cin >> x >> y >> u >> v; x--, y --, u --; sum += A[x] * ((v - u) - (R[x] - L[x])); sum += seg1.prod(L[x], R[x]); sum += seg2.get(idx[x]).value * A[x]; if (L[x] <= idx[x] && idx[x] < R[x]) { sum -= A[x]; } seg1.set(idx[x], 0); seg1.set(y, A[x]); seg2.apply(L[x], R[x], -1); seg2.apply(u, v, 1); sum -= seg1.prod(u, v); sum -= seg2.get(y).value * A[x]; if (u <= y && y < v) { sum += A[x]; } L[x] = u; R[x] = v; idx[x] = y; cout << sum << endl; } }