結果

問題 No.3265 地元に帰れば天才扱い!
ユーザー ts5208
提出日時 2025-09-06 14:22:03
言語 C++17(gnu拡張)
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 6,040 bytes
コンパイル時間 2,356 ms
コンパイル使用メモリ 211,140 KB
実行使用メモリ 17,184 KB
最終ジャッジ日時 2025-09-06 14:22:48
合計ジャッジ時間 8,523 ms
ジャッジサーバーID
(参考情報)
judge1 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3 TLE * 1
other -- * 21
権限があれば一括ダウンロードができます

ソースコード

diff #

// ======================== ORIGINAL PYTHON CODE (AS REQUIRED) ========================
// class BIT:
//     def __init__(self, size):
//         self.size = size
//         self.tree = [0] * (size + 1)
//     def add(self, index, value):
//         index += 1 
//         while index <= self.size:
//             self.tree[index] += value
//             index += index & -index
//     def sum(self, index):
//         index += 1
//         result = 0
//         while index > 0:
//             result += self.tree[index]
//
//             index -= index & -index
//         return result
//     def range_sum(self, left, right):
//         return self.sum(right - 1) - self.sum(left - 1)
// from heapq import heappop, heappush, heapify
// from bisect import bisect
// #from sortedcontainers import SortedList
// from collections import deque, defaultdict
// from math import floor, ceil, isqrt, comb
// from sys import stdin, setrecursionlimit
// #setrecursionlimit(10**7)
// intin = lambda: int(stdin.readline())
// strin = lambda: stdin.readline().rstrip()
// listin = lambda: list(map(int, stdin.readline().split()))
// tuplein = lambda m: [tuple(map(lambda x: int(x) if x.isdigit() or (len(x) > 1 and x[0] == "-" and x[1:].isdigit()) else x, stdin.readline().split())) for _ in range(m)]
// gridin = lambda m: [list(map(int, stdin.readline().split())) for _ in range(m)]
// strgridin = lambda h: [stdin.readline().rstrip() for _ in range(h)]
// mapin = lambda: map(int, stdin.readline().split())
// N, M = mapin()
// ALR = tuplein(N)
// Q = intin()
// XYUV = tuplein(Q)
// SA = 0
// SB = 0
// imos = BIT(M + 1)
// fenwick = BIT(M)
// LR = [(0, 0) for _ in range(M)]
// A = [0] * M
// for i, (a, l, r) in enumerate(ALR):
//     SA += (r - l + 1) * a
//     imos.add(l-1, 1)
//     imos.add(r, -1)
//     LR[i] = (l, r)
//     A[i] = a
//     fenwick.add(i, a)
// for i, (a, l, r) in enumerate(ALR):
//     SB += a * imos.range_sum(0, i + 1)
// for x, y, u, v in XYUV:
//     x -= 1; y -= 1
//     SA -= (LR[x][1] - LR[x][0] + 1) * A[x]
//     SB -= fenwick.range_sum(LR[x][0]-1, LR[x][1])
//     SB -= imos.range_sum(0, x + 1) * A[x]
//     if LR[x][0] - 1 <= x <= LR[x][1] - 1:
//         SB += A[x]
//     #print(fenwick.range_sum(LR[x][0]-1, LR[x][1]), imos.range_sum(0, x + 1) * A[x])
//     fenwick.add(x, -A[x])
//     imos.add(LR[x][0]-1, -1)
//     imos.add(LR[x][1], 1)
//     LR[x] = (0, 0)
//     A[y] = A[x]
//     A[x] = 0
//     imos.add(u-1, 1)
//     imos.add(v, -1)
//     fenwick.add(y, A[y])
//     LR[y] = (u, v)
//     SA += (v - u + 1) * A[y]
//     SB += fenwick.range_sum(u-1, v)
//     SB += imos.range_sum(0, y + 1) * A[y]
//     #print(SB, fenwick.range_sum(u-1, v), imos.range_sum(0, y + 1) * A[y])
//     if u - 1 <= y <= v - 1:
//         SB -= A[y]
//     #print(SA, SB)
//     #tmpls = []
//     #for i in range(M + 1):
//     #    tmpls.append(imos.range_sum(0, i))
//     #print(*tmpls)
//     print(SA-SB)
// ====================================================================================

#include <bits/stdc++.h>
using namespace std;

struct BIT {
    int size;
    vector<long long> tree; // 1-indexed internal tree
    BIT() {}
    BIT(int n) { init(n); }
    void init(int n) {
        size = n;
        tree.assign(size + 1, 0LL);
    }
    // add value at 0-based index
    void add(int index, long long value) {
        index += 1;
        while (index <= size) {
            tree[index] += value;
            index += index & -index;
        }
    }
    // sum over [0..index] (0-based, inclusive)
    long long sum(int index) const {
        index += 1;
        long long result = 0;
        while (index > 0) {
            result += tree[index];
            index -= index & -index;
        }
        return result;
    }
    // sum over [left, right) (0-based, half-open)
    long long range_sum(int left, int right) const {
        return sum(right - 1) - sum(left - 1);
    }
};

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

    int N, M;
    if (!(cin >> N >> M)) return 0;

    vector<tuple<long long,int,int>> ALR(N);
    for (int i = 0; i < N; ++i) {
        long long a; int l, r;
        cin >> a >> l >> r;
        ALR[i] = {a, l, r};
    }
    int Q; cin >> Q;
    vector<tuple<int,int,int,int>> XYUV(Q);
    for (int i = 0; i < Q; ++i) {
        int x, y, u, v;
        cin >> x >> y >> u >> v;
        XYUV[i] = {x, y, u, v};
    }

    long long SA = 0;
    long long SB = 0;

    BIT imos(M + 1); // indices 0..M are valid (because Python used M+1 size)
    BIT fenwick(M);  // indices 0..M-1

    vector<pair<int,int>> LR(M, {0,0});
    vector<long long> A(M, 0);

    for (int i = 0; i < N; ++i) {
        auto [a, l, r] = ALR[i];
        SA += 1LL * (r - l + 1) * a;
        imos.add(l - 1, 1);
        imos.add(r, -1);
        if (i < M) {
            LR[i] = {l, r};
            A[i] = a;
            fenwick.add(i, a);
        }
    }
    for (int i = 0; i < N; ++i) {
        auto [a, l, r] = ALR[i];
        SB += a * imos.range_sum(0, i + 1);
    }

    for (int qi = 0; qi < Q; ++qi) {
        int x, y, u, v;
        tie(x, y, u, v) = XYUV[qi];
        x -= 1; y -= 1;

        // Remove contribution of item x from SA and SB
        SA -= 1LL * (LR[x].second - LR[x].first + 1) * A[x];
        SB -= fenwick.range_sum(LR[x].first - 1, LR[x].second);
        SB -= imos.range_sum(0, x + 1) * A[x];
        if (LR[x].first - 1 <= x && x <= LR[x].second - 1) {
            SB += A[x];
        }

        fenwick.add(x, -A[x]);
        imos.add(LR[x].first - 1, -1);
        imos.add(LR[x].second, 1);
        LR[x] = {0, 0};

        A[y] = A[x];
        A[x] = 0;

        imos.add(u - 1, 1);
        imos.add(v, -1);
        fenwick.add(y, A[y]);
        LR[y] = {u, v};

        SA += 1LL * (v - u + 1) * A[y];
        SB += fenwick.range_sum(u - 1, v);
        SB += imos.range_sum(0, y + 1) * A[y];
        if (u - 1 <= y && y <= v - 1) {
            SB -= A[y];
        }

        cout << (SA - SB) << '\n';
    }

    return 0;
}
0