結果

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

ソースコード

diff # 

/*
from atcoder.segtree import SegTree
from atcoder.lazysegtree import LazySegTree

N, M = map(int, input().split())
ALR = [[int(x) for x in input().split()] for _ in range(N)]

# iwi[i]: 岩井星人のレート, 地元の左端, 地元の右端, 今いる家
iwi = [[ALR[i][0], ALR[i][1] - 1, ALR[i][2], i] for i in range(N)]

def plus(a, b):
    return a + b

# rate[i]: 家iのレート
rate_init = [ALR[i][0] if i < N else 0 for i in range(M)]
rate = SegTree(plus, 0, rate_init)

# jimoto[i]: 家iが地元である岩井星人の数
jimoto = LazySegTree(plus, 0, plus, plus, 0, [0] * M)
for _, l, r in ALR:
    jimoto.apply(l - 1, r, 1)

ans = sum(iwi[i][0] * (iwi[i][2] - iwi[i][1]) for i in range(N)) - sum(rate.get(i) * jimoto.get(i) for i in range(M))

for _ in range(int(input())):
    x, y, u, v = map(int, input().split())
    x -= 1; y -= 1; u -= 1
    y_old = iwi[x][3]
    # 元の天才度を引く
    ans -= iwi[x][0] * (iwi[x][2] - iwi[x][1]) - rate.prod(iwi[x][1], iwi[x][2])
    # 星人xがいなくなった分、他の星人の天才度が増す
    jimoto.apply(iwi[x][1], iwi[x][2], -1)
    ans += iwi[x][0] * jimoto.get(iwi[x][3])
    # 星人xが来た分、他の星人の天才度が減る
    ans -= iwi[x][0] * jimoto.get(y)
    jimoto.apply(u, v, 1)
    # 新しい天才度を足す
    rate.set(iwi[x][3], 0)
    rate.set(y, iwi[x][0])
    ans += iwi[x][0] * (v - u) - rate.prod(u, v)
    # 情報を更新する
    iwi[x][1] = u
    iwi[x][2] = v
    iwi[x][3] = y

    print(ans)
*/

#include <bits/stdc++.h>
#include <atcoder/segtree>
#include <atcoder/lazysegtree>
using namespace std;
using ll = long long;

// S-type operations for both segment trees
ll opS(ll a, ll b) { return a + b; }
ll eS()            { return 0; }

// F-type (lazy) operations: mapping and composition
ll mappingF(ll f, ll x)      { return x + f; }
ll compositionF(ll f, ll g)  { return f + g; }
ll idF()                     { return 0; }

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

    int N, M;
    cin >> N >> M;

    vector<array<ll,3>> ALR(N);
    for (int i = 0; i < N; i++) {
        cin >> ALR[i][0] >> ALR[i][1] >> ALR[i][2];
    }

    // iwi[i] = {rate, local_l (0-index), local_r (exclusive), current_house}
    vector<array<ll,4>> iwi(N);
    for (int i = 0; i < N; i++) {
        iwi[i] = { ALR[i][0],
                   ALR[i][1] - 1,
                   ALR[i][2],
                   (ll)i };
    }

    // rate[i]: rate at house i
    vector<ll> rate_init(M, 0);
    for (int i = 0; i < N; i++) {
        rate_init[i] = ALR[i][0];
    }
    atcoder::segtree<ll, opS, eS> rate(rate_init);

    // jimoto[i]: number of aliens whose local region covers house i
    vector<ll> jimoto_init(M, 0);
    atcoder::lazy_segtree<ll, opS, eS, ll, mappingF, compositionF, idF> jimoto(jimoto_init);

    // build initial local counts
    for (int i = 0; i < N; i++) {
        ll l = ALR[i][1] - 1;
        ll r = ALR[i][2];
        jimoto.apply(l, r, 1);
    }

    // initial answer
    ll ans = 0;
    for (int i = 0; i < N; i++) {
        ans += iwi[i][0] * (iwi[i][2] - iwi[i][1]);
    }
    for (int i = 0; i < M; i++) {
        ans -= rate.get(i) * jimoto.get(i);
    }

    int Q;
    cin >> Q;
    while (Q--) {
        ll x, y, u, v;
        cin >> x >> y >> u >> v;
        x--; y--; u--; // maintain right bound v as exclusive

        // remove old genius contribution
        ans -= iwi[x][0] * (iwi[x][2] - iwi[x][1])
             - rate.prod(iwi[x][1], iwi[x][2]);

        // x leaves its local region
        jimoto.apply(iwi[x][1], iwi[x][2], -1);
        ans += iwi[x][0] * jimoto.get(iwi[x][3]);

        // arrival effect at new house y
        ans -= iwi[x][0] * jimoto.get(y);

        // x arrives at new local region [u, v)
        jimoto.apply(u, v, 1);

        // update rate segment
        rate.set(iwi[x][3], 0);
        rate.set(y, iwi[x][0]);

        // add new genius contribution
        ans += iwi[x][0] * (v - u)
             - rate.prod(u, v);

        // update metadata for alien x
        iwi[x][1] = u;
        iwi[x][2] = v;
        iwi[x][3] = y;

        cout << ans << "\n";
    }

    return 0;
}
0