結果

問題 No.3265 地元に帰れば天才扱い！
コンテスト
ユーザー srjywrdnprkt
提出日時 2025-10-20 17:09:19
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 272 ms / 2,500 ms
コード長 1,950 bytes
コンパイル時間 3,167 ms
コンパイル使用メモリ 282,436 KB
実行使用メモリ 12,672 KB
最終ジャッジ日時 2025-10-20 17:09:38
合計ジャッジ時間 17,118 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/fenwicktree>

using namespace std;
using namespace atcoder;
using ll = long long;
//using mint = modint998244353;

int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    /*
       差分を考える。
       X_kが元々住んでいた家をZ_kとする。
       (R-L+1) * A_k - [L, R]のレートの和だけ減少、
       Z_kを地元として含むX_k以外の岩井の数*A_kだけ増加し、
       引越し後は、
       (V-U+1) * A_k - [U, V]のレートの和だけ増加、
       と
       Y_kを地元として含むX_k以外の岩井の数*A_kだけ減少する。
       だけ天才度の和が増加する。

       range add point sumで家xを含む区間の数。
       point add range sumで区間[U, V]内のレートの和を求める。
    */

    ll N, M, Q, ans=0;
    cin >> N >> M;
    vector<ll> A(N), L(N), R(N);
    fenwick_tree<ll> tc(M+1), ts(M+1);
    vector<ll> where(N); //iが住んでいる家の番号
    for (int i=0; i<N; i++){
        cin >> A[i] >> L[i] >> R[i];
        L[i]--;
        R[i]--;
        tc.add(L[i], 1);
        tc.add(R[i]+1, -1);
        ts.add(i, A[i]);
        where[i] = i;
    }

    for (int i=0; i<N; i++) ans += (R[i]-L[i]+1) * A[i] - ts.sum(L[i], R[i]+1);

    cin >> Q;
    while(Q--){
        ll X, Y, U, V, Z;
        cin >> X >> Y >> U >> V;
        X--; Y--; U--; V--;
        ans -= (R[X]-L[X]+1) * A[X] - ts.sum(L[X], R[X]+1);
        Z = where[X];
        ans += (tc.sum(0, Z+1)-(L[X] <= Z && Z <= R[X])) * A[X];
        where[X] = Y;
        ts.add(Z, -A[X]);
        ts.add(Y, A[X]);
        tc.add(L[X], -1);
        tc.add(R[X]+1, 1);
        L[X] = U; R[X] = V;
        tc.add(L[X], 1);
        tc.add(R[X]+1, -1);
        ans += (R[X]-L[X]+1) * A[X] - ts.sum(L[X], R[X]+1);
        ans -= (tc.sum(0, Y+1)-(L[X] <= Y && Y <= R[X])) * A[X];
        cout << ans << '\n';
    }

    return 0;
}
0