結果
問題 |
No.3265 地元に帰れば天才扱い!
|
ユーザー |
|
提出日時 | 2025-09-06 14:23:37 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 697 ms / 2,500 ms |
コード長 | 1,649 bytes |
コンパイル時間 | 4,914 ms |
コンパイル使用メモリ | 257,348 KB |
実行使用メモリ | 16,592 KB |
最終ジャッジ日時 | 2025-09-06 14:24:02 |
合計ジャッジ時間 | 22,263 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define rep(i, s, t) for (ll i = s; i < (ll)(t); i++) #define all(x) begin(x), end(x) template <class T> bool chmin(T& x, T y) { return x > y ? (x = y, true) : false; } template <class T> bool chmax(T& x, T y) { return x < y ? (x = y, true) : false; } struct io_setup { io_setup() { ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(15); } } io_setup; #include <atcoder/all> // template atcoder lazy segtree using S = ll; S op(S a, S b) { return max(a, b); } S e() { return 0; } using F = ll; S mapping(F f, S x) { return f + x; } F comp(F f, F g) { return f + g; } F id() { return 0; } using segtree = atcoder::lazy_segtree<S, op, e, F, mapping, comp, id>; void solve() { int n, m; cin >> n >> m; vector<ll> a(n), l(n), r(n); rep(i, 0, n) cin >> a[i] >> l[i] >> r[i], l[i]--; vector<int> p(n); iota(p.begin(), p.end(), 0); segtree seg(m); atcoder::fenwick_tree<ll> ft(m); ll ans = 0; rep(i, 0, n) { seg.apply(l[i], r[i], 1); ft.add(p[i], a[i]); ans += a[i] * (r[i] - l[i]); } rep(i, 0, m) ans -= ft.sum(i, i + 1) * seg.get(i); int q; cin >> q; rep(Qi, 0, q) { int x, y, u, v; cin >> x >> y >> u >> v; x--, y--, u--; ans += a[x] * seg.get(p[x]); ft.add(p[x], -a[x]); ft.add(y, a[x]); ans -= a[x] * seg.get(y); ans += ft.sum(l[x], r[x]); seg.apply(l[x], r[x], -1); seg.apply(u, v, 1); ans -= ft.sum(u, v); ans -= a[x] * (r[x] - l[x]); ans += a[x] * (v - u); p[x] = y; l[x] = u, r[x] = v; cout << ans << "\n"; } } int main() { int t = 1; // cin >> t; while (t--) solve(); }