結果

問題 No.3265 地元に帰れば天才扱い！
ユーザー a01sa01to
提出日時 2025-09-15 00:59:40
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 269 ms / 2,500 ms
コード長 1,293 bytes
コンパイル時間 2,860 ms
コンパイル使用メモリ 289,556 KB
実行使用メモリ 10,240 KB
最終ジャッジ日時 2025-09-15 00:59:57
合計ジャッジ時間 15,570 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
using ll = long long;
using ull = unsigned long long;

#include <atcoder/fenwicktree>

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  atcoder::fenwick_tree<int> cnt(m + 1);
  atcoder::fenwick_tree<ll> sum(m + 1);
  vector<tuple<ll, int, int>> a(n);
  vector<ll> rate(n);
  ll ans = 0;
  rep(i, n) {
    int x, y, z;
    cin >> x >> y >> z;
    --y;
    a[i] = { i, y, z };
    rate[i] = x;
    sum.add(i, x), cnt.add(y, 1), cnt.add(z, -1);
    ans += (ll) (z - y) * x;
  }
  rep(i, m) ans -= (ll) cnt.sum(0, i + 1) * sum.sum(i, i + 1);
  cerr << ans << '\n';

  int q;
  cin >> q;
  while (q--) {
    int x, y, l, r;
    cin >> x >> y >> l >> r;
    --x, --y, --l;
    auto [prvi, prvl, prvr] = a[x];
    a[x] = { y, l, r };

    ans -= (prvr - prvl) * rate[x];
    ans += sum.sum(prvl, prvr);
    ans += (cnt.sum(0, prvi + 1) + !(prvl <= prvi && prvi < prvr)) * rate[x];
    sum.add(prvi, -rate[x]), cnt.add(prvl, -1), cnt.add(prvr, 1);

    sum.add(y, rate[x]), cnt.add(l, 1), cnt.add(r, -1);
    ans += (r - l) * rate[x];
    ans -= sum.sum(l, r);
    ans -= (cnt.sum(0, y + 1) + !(l <= y && y < r)) * rate[x];

    cout << ans << '\n';
  }
  return 0;
}
0