結果

問題 No.3265 地元に帰れば天才扱い!
ユーザー iastm
提出日時 2025-09-06 14:25:43
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,044 ms / 2,500 ms
コード長 1,358 bytes
コンパイル時間 1,016 ms
コンパイル使用メモリ 93,804 KB
実行使用メモリ 9,472 KB
最終ジャッジ日時 2025-09-06 14:26:11
合計ジャッジ時間 26,945 ms
ジャッジサーバーID
(参考情報)
judge / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <iostream>
#include <vector>
#include <atcoder/fenwicktree>

int main() {
    int N, M;
    std::cin >> N >> M;
    int64_t total_rating = 0, total_diff = 0;
    atcoder::fenwick_tree<int64_t> count(M + 1), rating(M + 1);
    std::vector<int> home(N), A(N), L(N), R(N);
    for (int i = 0; i < N; i++) {
        std::cin >> A[i] >> L[i] >> R[i];
        L[i]--;
        total_rating += A[i] * int64_t(R[i] - L[i]);
        home[i] = i;
        count.add(L[i], 1);
        count.add(R[i], -1);
        rating.add(i, A[i]);
    }
    for (int i = 0; i < N; i++) {
        total_diff += A[i] * count.sum(0, home[i] + 1);
    }

    int Q;
    std::cin >> Q;
    while (Q--) {
        int X, Y, U, V;
        std::cin >> X >> Y >> U >> V;
        X--, Y--, U--;
        total_rating -= A[X] * int64_t(R[X] - L[X]);
        total_diff -= A[X] * count.sum(0, home[X] + 1);
        rating.add(home[X], -A[X]);
        total_diff -= rating.sum(L[X], R[X]);
        total_diff += rating.sum(U, V);
        rating.add(Y, A[X]);
        count.add(L[X], -1);
        count.add(R[X], 1);
        home[X] = Y;
        L[X] = U;
        R[X] = V;
        count.add(U, 1);
        count.add(V, -1);
        total_rating += A[X] * int64_t(V - U);
        total_diff += A[X] * count.sum(0, Y + 1);
        std::cout << total_rating - total_diff << std::endl;
    }
}
0