結果
問題 |
No.3265 地元に帰れば天才扱い!
|
ユーザー |
|
提出日時 | 2025-09-06 15:24:44 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,159 ms / 2,500 ms |
コード長 | 1,787 bytes |
コンパイル時間 | 4,206 ms |
コンパイル使用メモリ | 291,812 KB |
実行使用メモリ | 26,120 KB |
最終ジャッジ日時 | 2025-09-06 15:25:31 |
合計ジャッジ時間 | 29,555 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/lazysegtree> #include <atcoder/segtree> using namespace std; using namespace atcoder; // --- LazySegTree 用の型定義 --- using S = long long; using F = long long; // 区間和 S op1(S a, S b) { return a + b; } S e() { return 0LL; } // LazySegTree の作用 S mapping1(F f, S x) { return f + x; } F composition1(F f, F g) { return f + g; } F id() { return 0LL; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; // LazySegTree と SegTree を初期化 lazy_segtree<S, op1, e, F, mapping1, composition1, id> kinnzyo(m + 1); segtree<S, op1, e> rate(m + 1); // Python の iwai_dict を C++ では map<int, tuple<int,int,int>> で持つ map<int, tuple<int, int, int, int>> iwai_dict; for (int i = 0; i < n; i++) { int a, l, r; cin >> a >> l >> r; int idx = i + 1; rate.set(idx, a); kinnzyo.apply(l, r + 1, 1); iwai_dict[idx] = {idx, a, l, r}; } long long ans = 0; for (int i = 1; i <= n; i++) { auto [prev, a, l, r] = iwai_dict[i]; ans += (long long)(r - l + 1) * a - rate.prod(l, r + 1); } int q; cin >> q; while (q--) { int x, y, u, v; cin >> x >> y >> u >> v; auto [prev, a, l, r] = iwai_dict[x]; ans -= (long long)(r - l + 1) * a - rate.prod(l, r + 1); rate.set(prev, 0); kinnzyo.apply(l, r + 1, -1); ans += kinnzyo.prod(prev, prev + 1) * a; ans -= kinnzyo.prod(y, y + 1) * a; kinnzyo.apply(u, v + 1, 1); rate.set(y, a); iwai_dict[x] = {y, a, u, v}; ans += (long long)(v - u + 1) * a - rate.prod(u, v + 1); cout << ans << "\n"; } return 0; }