結果
問題 |
No.3265 地元に帰れば天才扱い!
|
ユーザー |
![]() |
提出日時 | 2025-09-06 14:03:49 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 331 ms / 2,500 ms |
コード長 | 1,706 bytes |
コンパイル時間 | 3,437 ms |
コンパイル使用メモリ | 302,948 KB |
実行使用メモリ | 8,704 KB |
最終ジャッジ日時 | 2025-09-06 14:04:05 |
合計ジャッジ時間 | 13,907 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 21 |
ソースコード
#include<bits/stdc++.h> namespace { #pragma GCC diagnostic ignored "-Wunused-function" #include<atcoder/all> #pragma GCC diagnostic warning "-Wunused-function" using namespace std; using namespace atcoder; #define rep(i,n) for(int i = 0; i < (int)(n); i++) #define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--) #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; } template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; } using ll = long long; using P = pair<int,int>; using VI = vector<int>; using VVI = vector<VI>; using VL = vector<ll>; using VVL = vector<VL>; } int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; fenwick_tree<int> cf0(m + 1); fenwick_tree<ll> pt1(m); VI a(n), l(n), r(n), x(n); rep(i, n) cin >> a[i] >> l[i] >> r[i], l[i]--, x[i] = i; auto f = [&](int i) { ll res = 0; res += ll(r[i] - l[i]) * a[i] - pt1.sum(l[i], r[i]); res -= (ll)cf0.sum(0, x[i] + 1) * a[i]; if (l[i] <= x[i] && x[i] < r[i]) res += a[i]; return res; }; rep(i, n) { pt1.add(x[i], a[i]); cf0.add(l[i], 1); cf0.add(r[i], -1); } ll ans = 0; rep(i, n) ans += ll(r[i] - l[i]) * a[i] - pt1.sum(l[i], r[i]); int q; cin >> q; rep(_, q) { int i, j, ui, vi; cin >> i >> j >> ui >> vi; i--, j--, ui--; ans -= f(i); pt1.add(x[i], -a[i]); cf0.add(l[i], -1); cf0.add(r[i], 1); x[i] = j; l[i] = ui; r[i] = vi; pt1.add(x[i], a[i]); cf0.add(l[i], 1); cf0.add(r[i], -1); ans += f(i); cout << ans << '\n'; } }