結果
問題 |
No.3265 地元に帰れば天才扱い!
|
ユーザー |
![]() |
提出日時 | 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; }