結果
| 問題 | 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 |
ソースコード
// ======================== 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;
}