結果

問題 No.3265 地元に帰れば天才扱い！
ユーザー Akidai
提出日時 2025-09-06 15:01:11
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 638 ms / 2,500 ms
コード長 2,748 bytes
コンパイル時間 4,701 ms
コンパイル使用メモリ 258,432 KB
実行使用メモリ 22,816 KB
最終ジャッジ日時 2025-09-06 15:01:36
合計ジャッジ時間 21,992 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = (1LL << 62) - (1LL << 31) - 1;

#define REP(i, init, n) for(int i = (int)(init); i < (int)(n); i++)
#define RREP(i, init, n) for(int i = (int)(init); i >= (int)(n); i--)
#define All(A) A.begin(), A.end()
#define rAll(A) A.rbegin(), A.rend()

#define vi vector<int>
#define vl vector<long>
#define vvi vector<vector<int>>
#define vvl vector<vector<long>>
#define pint pair<int, int>
#define plong pair<long, long>

int N, M, Q;
vl A;
vector<plong> LR;
vvi P;

void solve() {
    long sum = 0;
    fenwick_tree<long> jimoto(M + 1), house(M + 1);
    vi idx(N, -1);
    REP(i, 0, N) {
        idx[i] = i;
        house.add(i, A[i]);
    } 

    REP(i, 0, N) {
        int L = LR[i].first;
        int R = LR[i].second;
        sum += A[i] * (R - L);
        jimoto.add(L, 1);
        jimoto.add(R, -1);
    }
    REP(i, 0, N) {
        long cnt = jimoto.sum(0, i + 1);
        sum -= cnt * A[i];
    }

    cerr << sum << endl;

    REP(i, 0, Q) {
        int x = P[i][0];
        int y = P[i][1];
        int u = P[i][2];
        int v = P[i][3];

        int house_idx = idx[x];
        long jimoto_cnt = jimoto.sum(0, house_idx + 1);
        sum += jimoto_cnt * A[x];
        sum -= A[x] * (LR[x].second - LR[x].first);

        jimoto.add(LR[x].first, -1);
        jimoto.add(LR[x].second, 1);
        house.add(house_idx, -A[x]);
        long house_sum = house.sum(LR[x].first, LR[x].second);
        sum += house_sum;
        // cerr << sum << endl;
        /*
        REP(i, 0, M) {
            cerr << jimoto.sum(0, i + 1) << " ";
        }
        cerr << endl;
        */

        idx[x] = y;
        LR[x] = {u, v};

        jimoto.add(LR[x].first, 1);
        jimoto.add(LR[x].second, -1);
        house_sum = house.sum(LR[x].first, LR[x].second);
        sum -= house_sum;

        house.add(y, A[x]);
        sum += A[x] * (LR[x].second - LR[x].first);
        jimoto_cnt = jimoto.sum(0, y + 1);
        sum -= jimoto_cnt * A[x];

        // cerr << house_sum << " " << jimoto_cnt << endl;

        cout << sum << endl;
        /*
        REP(i, 0, M) {
            cerr << jimoto.sum(0, i + 1) << " ";
        }
        cerr << endl;
        */
    }
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    cin >> N >> M;
    A.resize(N);
    LR.resize(N);
    REP(i, 0, N) {
        cin >> A[i];
        cin >> LR[i].first >> LR[i].second;
        LR[i].first--;
    }
    cin >> Q;
    P.resize(Q);
    REP(i, 0, Q) {
        int x, y, u, v;
        cin >> x >> y >> u >> v;
        x--; y--; u--;
        P[i] = {x, y, u, v};
    }
    solve();
}
0