結果
| 問題 |
No.3265 地元に帰れば天才扱い！
|
| コンテスト | |
| ユーザー |
 kmmtkm
|
| 提出日時 | 2025-09-06 14:57:05 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 915 ms / 2,500 ms |
| コード長 | 19,373 bytes |
| コンパイル時間 | 1,362 ms |
| コンパイル使用メモリ | 130,820 KB |
| 実行使用メモリ | 25,900 KB |
| 最終ジャッジ日時 | 2025-09-06 14:57:33 |
| 合計ジャッジ時間 | 23,129 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 21 |
ソースコード
/*
Original Python Code:
# 自作ライブラリ
# https://github.com/takumi-okamoto/competitive-programming-public/tree/main/mylib
import sys
# from atcoder.fenwicktree import FenwickTree
# from atcoder.lazysegtree import LazySegTree
# sys.setrecursionlimit(10**8)
import typing
# https://github.com/not522/ac-library-python/blob/master/atcoder/fenwicktree.py
class FenwickTree:
"""Reference: https://en.wikipedia.org/wiki/Fenwick_tree"""
def __init__(self, n: int = 0) -> None:
self._n = n
self.data = [0] * n
def add(self, p: int, x: typing.Any) -> None:
assert 0 <= p < self._n
p += 1
while p <= self._n:
self.data[p - 1] += x
p += p & -p
def sum(self, left: int, right: int) -> typing.Any:
assert 0 <= left <= right <= self._n
return self._sum(right) - self._sum(left)
def _sum(self, r: int) -> typing.Any:
s = 0
while r > 0:
s += self.data[r - 1]
r -= r & -r
return s
# https://github.com/not522/ac-library-python/blob/master/atcoder/_bit.py
def _ceil_pow2(n: int) -> int:
x = 0
while (1 << x) < n:
x += 1
return x
# https://github.com/not522/ac-library-python/blob/master/atcoder/lazysegtree.py
# を一部改変
class LazySegTree:
def __init__(
self,
op: typing.Callable[[typing.Any, typing.Any], typing.Any],
e: typing.Any,
mapping: typing.Callable[[typing.Any, typing.Any], typing.Any],
composition: typing.Callable[[typing.Any, typing.Any], typing.Any],
id_: typing.Any,
v: typing.Union[int, typing.List[typing.Any]],
) -> None:
self._op = op
self._e = e
self._mapping = mapping
self._composition = composition
self._id = id_
if isinstance(v, int):
v = [e] * v
self._n = len(v)
self._log = _ceil_pow2(self._n)
self._size = 1 << self._log
self._d = [e] * (2 * self._size)
self._lz = [self._id] * self._size
for i in range(self._n):
self._d[self._size + i] = v[i]
for i in range(self._size - 1, 0, -1):
self._update(i)
def set(self, p: int, x: typing.Any) -> None:
assert 0 <= p < self._n
p += self._size
for i in range(self._log, 0, -1):
self._push(p >> i)
self._d[p] = self._mapping(f, self._d[p])
for i in range(1, self._log + 1):
self._update(p >> i)
def get(self, p: int) -> typing.Any:
assert 0 <= p < self._n
p += self._size
for i in range(self._log, 0, -1):
self._push(p >> i)
return self._d[p]
def prod(self, left: int, right: int) -> typing.Any:
assert 0 <= left <= right <= self._n
if left == right:
return self._e
left += self._size
right += self._size
for i in range(self._log, 0, -1):
if ((left >> i) << i) != left:
self._push(left >> i)
if ((right >> i) << i) != right:
self._push((right - 1) >> i)
sml = self._e
smr = self._e
while left < right:
if left & 1:
sml = self._op(sml, self._d[left])
left += 1
if right & 1:
right -= 1
smr = self._op(self._d[right], smr)
left >>= 1
right >>= 1
return self._op(sml, smr)
def all_prod(self) -> typing.Any:
return self._d[1]
def apply(
self,
left: int,
right: typing.Optional[int] = None,
f: typing.Optional[typing.Any] = None,
) -> None:
assert f is not None
if right is None:
p = left
assert 0 <= left < self._n
p += self._size
for i in range(self._log, 0, -1):
self._push(p >> i)
self._d[p] = self._mapping(f, self._d[p])
for i in range(1, self._log + 1):
self._update(p >> i)
else:
assert 0 <= left <= right <= self._n
if left == right:
return
left += self._size
right += self._size
for i in range(self._log, 0, -1):
if ((left >> i) << i) != left:
self._push(left >> i)
if ((right >> i) << i) != right:
self._push((right - 1) >> i)
l2 = left
r2 = right
while left < right:
if left & 1:
self._all_apply(left, f)
left += 1
if right & 1:
right -= 1
self._all_apply(right, f)
left >>= 1
right >>= 1
left = l2
right = r2
for i in range(1, self._log + 1):
if ((left >> i) << i) != left:
self._update(left >> i)
if ((right >> i) << i) != right:
self._update((right - 1) >> i)
def max_right(self, left: int, g: typing.Callable[[typing.Any], bool]) -> int:
assert 0 <= left <= self._n
assert g(self._e)
if left == self._n:
return self._n
left += self._size
for i in range(self._log, 0, -1):
self._push(left >> i)
sm = self._e
first = True
while first or (left & -left) != left:
first = False
while left % 2 == 0:
left >>= 1
if not g(self._op(sm, self._d[left])):
while left < self._size:
self._push(left)
left *= 2
if g(self._op(sm, self._d[left])):
sm = self._op(sm, self._d[left])
left += 1
return left - self._size
sm = self._op(sm, self._d[left])
left += 1
return self._n
def min_left(self, right: int, g: typing.Any) -> int:
assert 0 <= right <= self._n
assert g(self._e)
if right == 0:
return 0
right += self._size
for i in range(self._log, 0, -1):
self._push((right - 1) >> i)
sm = self._e
first = True
while first or (right & -right) != right:
first = False
right -= 1
while right > 1 and right % 2:
right >>= 1
if not g(self._op(self._d[right], sm)):
while right < self._size:
self._push(right)
right = 2 * right + 1
if g(self._op(self._d[right], sm)):
sm = self._op(self._d[right], sm)
right -= 1
return right + 1 - self._size
sm = self._op(self._d[right], sm)
return 0
def _update(self, k: int) -> None:
self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1])
def _all_apply(self, k: int, f: typing.Any) -> None:
self._d[k] = self._mapping(f, self._d[k])
if k < self._size:
self._lz[k] = self._composition(f, self._lz[k])
def _push(self, k: int) -> None:
self._all_apply(2 * k, self._lz[k])
self._all_apply(2 * k + 1, self._lz[k])
self._lz[k] = self._id
def debug(*args):
print(*args, file=sys.stderr)
def main():
n, m = map(int, input().split())
a = []
l = []
r = []
for _ in range(n):
ai, li, ri = map(int, input().split())
a.append(ai)
l.append(li - 1)
r.append(ri)
b = FenwickTree(m)
for i in range(n):
b.add(i, a[i])
INF = 10**18
counter = LazySegTree(
op=lambda v1, v2: min(v1, v2),
mapping=lambda f, v: f + v,
composition=lambda f, g: f + g,
e=INF,
id_=0,
v=[0] * m,
)
# 初期化
ans = 0
pos = [None] * m
inv_pos = dict()
for i in range(n):
ai, li, ri = a[i], l[i], r[i]
ans += ai * (ri - li) - b.sum(li, ri)
counter.apply(li, ri, 1)
pos[i] = i
inv_pos[i] = i
# debug(ans)
# debug(counter)
# debug("counter", [counter.get(i) for i in range(m)])
# debug("b", [b.sum(i, i + 1) for i in range(m)])
q = int(input())
for _ in range(q):
x, y, u, v = map(int, input().split())
x -= 1
y -= 1
u -= 1
# 自分のレートの幅の差分
ans += a[x] * (v - u) - a[x] * (r[x] - l[x])
# 自分に対する相対基準の幅の差分
ans += b.sum(l[x], r[x])
pre_house = pos[x]
# 自分が相対基準だったとこ
counter.apply(l[x], r[x], -1)
ans += a[x] * counter.get(pre_house)
# 自分が相対基準になるところ
ans -= a[x] * counter.get(y)
counter.apply(u, v, 1)
# お家の移動
b.add(pre_house, -a[x])
b.add(y, a[x])
ans -= b.sum(u, v)
pos[x] = y
inv_pos[y] = x
l[x], r[x] = u, v
print(ans)
# debug("counter", [counter.get(i) for i in range(m)])
# debug("b", [b.sum(i, i + 1) for i in range(m)])
if __name__ == "__main__":
main()
*/
#include <iostream>
#include <vector>
#include <functional>
#include <numeric>
#include <algorithm>
#include <map>
#include <cassert>
// Reference: https://en.wikipedia.org/wiki/Fenwick_tree
class FenwickTree {
private:
int _n;
std::vector<long long> data;
long long _sum(int r) {
long long s = 0;
while (r > 0) {
s += data[r - 1];
r -= r & -r;
}
return s;
}
public:
FenwickTree(int n = 0) : _n(n), data(n, 0) {}
void add(int p, long long x) {
assert(0 <= p && p < _n);
p++;
while (p <= _n) {
data[p - 1] += x;
p += p & -p;
}
}
long long sum(int left, int right) {
assert(0 <= left && left <= right && right <= _n);
return _sum(right) - _sum(left);
}
};
int ceil_pow2(int n) {
int x = 0;
while ((1 << x) < n) {
x++;
}
return x;
}
template <class S, class F,
class Op, class Mapping, class Composition>
class LazySegTree {
private:
int _n;
int _log;
int _size;
std::vector<S> _d;
std::vector<F> _lz;
Op _op;
S _e;
Mapping _mapping;
Composition _composition;
F _id;
void _update(int k) {
_d[k] = _op(_d[2 * k], _d[2 * k + 1]);
}
void _all_apply(int k, F f) {
_d[k] = _mapping(f, _d[k]);
if (k < _size) {
_lz[k] = _composition(f, _lz[k]);
}
}
void _push(int k) {
_all_apply(2 * k, _lz[k]);
_all_apply(2 * k + 1, _lz[k]);
_lz[k] = _id;
}
public:
LazySegTree(int n, Op op, S e, Mapping mapping, Composition composition, F id)
: _n(n), _op(op), _e(e), _mapping(mapping), _composition(composition), _id(id) {
_log = ceil_pow2(_n);
_size = 1 << _log;
_d.assign(2 * _size, _e);
_lz.assign(_size, _id);
}
LazySegTree(const std::vector<S>& v, Op op, S e, Mapping mapping, Composition composition, F id)
: _n(v.size()), _op(op), _e(e), _mapping(mapping), _composition(composition), _id(id) {
_log = ceil_pow2(_n);
_size = 1 << _log;
_d.assign(2 * _size, _e);
_lz.assign(_size, _id);
for (int i = 0; i < _n; i++) {
_d[_size + i] = v[i];
}
for (int i = _size - 1; i > 0; i--) {
_update(i);
}
}
void set(int p, S x) {
assert(0 <= p && p < _n);
p += _size;
for (int i = _log; i > 0; i--) {
_push(p >> i);
}
_d[p] = x;
for (int i = 1; i <= _log; i++) {
_update(p >> i);
}
}
S get(int p) {
assert(0 <= p && p < _n);
p += _size;
for (int i = _log; i > 0; i--) {
_push(p >> i);
}
return _d[p];
}
S prod(int left, int right) {
assert(0 <= left && left <= right && right <= _n);
if (left == right) {
return _e;
}
left += _size;
right += _size;
for (int i = _log; i > 0; i--) {
if (((left >> i) << i) != left) _push(left >> i);
if (((right >> i) << i) != right) _push((right - 1) >> i);
}
S sml = _e, smr = _e;
while (left < right) {
if (left & 1) {
sml = _op(sml, _d[left]);
left++;
}
if (right & 1) {
right--;
smr = _op(_d[right], smr);
}
left >>= 1;
right >>= 1;
}
return _op(sml, smr);
}
S all_prod() {
return _d[1];
}
void apply(int p, F f) {
assert(0 <= p && p < _n);
p += _size;
for (int i = _log; i > 0; i--) {
_push(p >> i);
}
_d[p] = _mapping(f, _d[p]);
for (int i = 1; i <= _log; i++) {
_update(p >> i);
}
}
void apply(int left, int right, F f) {
assert(0 <= left && left <= right && right <= _n);
if (left == right) {
return;
}
left += _size;
right += _size;
for (int i = _log; i > 0; i--) {
if (((left >> i) << i) != left) _push(left >> i);
if (((right >> i) << i) != right) _push((right - 1) >> i);
}
{
int l2 = left;
int r2 = right;
while (left < right) {
if (left & 1) {
_all_apply(left, f);
left++;
}
if (right & 1) {
right--;
_all_apply(right, f);
}
left >>= 1;
right >>= 1;
}
left = l2;
right = r2;
}
for (int i = 1; i <= _log; i++) {
if (((left >> i) << i) != left) _update(left >> i);
if (((right >> i) << i) != right) _update((right - 1) >> i);
}
}
int max_right(int left, std::function<bool(S)> g) {
assert(0 <= left && left <= _n);
assert(g(_e));
if (left == _n) {
return _n;
}
left += _size;
for (int i = _log; i > 0; i--) {
_push(left >> i);
}
S sm = _e;
bool first = true;
while (first || (left & -left) != left) {
first = false;
while (left % 2 == 0) {
left >>= 1;
}
if (!g(_op(sm, _d[left]))) {
while (left < _size) {
_push(left);
left *= 2;
if (g(_op(sm, _d[left]))) {
sm = _op(sm, _d[left]);
left++;
}
}
return left - _size;
}
sm = _op(sm, _d[left]);
left++;
}
return _n;
}
int min_left(int right, std::function<bool(S)> g) {
assert(0 <= right && right <= _n);
assert(g(_e));
if (right == 0) {
return 0;
}
right += _size;
for (int i = _log; i > 0; i--) {
_push((right - 1) >> i);
}
S sm = _e;
bool first = true;
while (first || (right & -right) != right) {
first = false;
right--;
while (right > 1 && right % 2) {
right >>= 1;
}
if (!g(_op(_d[right], sm))) {
while (right < _size) {
_push(right);
right = 2 * right + 1;
if (g(_op(_d[right], sm))) {
sm = _op(_d[right], sm);
right--;
}
}
return right + 1 - _size;
}
sm = _op(_d[right], sm);
}
return 0;
}
};
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n, m;
std::cin >> n >> m;
std::vector<long long> a(n);
std::vector<int> l(n);
std::vector<int> r(n);
for (int i = 0; i < n; ++i) {
std::cin >> a[i] >> l[i] >> r[i];
l[i]--;
}
FenwickTree b(m);
for (int i = 0; i < n; ++i) {
b.add(i, a[i]);
}
const long long INF = 1000000000000000000LL;
auto op = [](long long v1, long long v2) { return std::min(v1, v2); };
auto mapping = [](long long f, long long v) { return f + v; };
auto composition = [](long long f, long long g) { return f + g; };
std::vector<long long> initial_v(m, 0);
LazySegTree<long long, long long, decltype(op), decltype(mapping), decltype(composition)>
counter(initial_v, op, INF, mapping, composition, 0);
long long ans = 0;
std::vector<int> pos(n);
std::map<int, int> inv_pos;
for (int i = 0; i < n; ++i) {
long long ai = a[i];
int li = l[i];
int ri = r[i];
ans += ai * (ri - li) - b.sum(li, ri);
counter.apply(li, ri, 1LL);
pos[i] = i;
inv_pos[i] = i;
}
int q;
std::cin >> q;
for (int i = 0; i < q; ++i) {
int x, y, u, v;
std::cin >> x >> y >> u >> v;
x--;
y--;
u--;
ans += a[x] * (v - u) - a[x] * (r[x] - l[x]);
ans += b.sum(l[x], r[x]);
int pre_house = pos[x];
counter.apply(l[x], r[x], -1LL);
ans += a[x] * counter.get(pre_house);
ans -= a[x] * counter.get(y);
counter.apply(u, v, 1LL);
b.add(pre_house, -a[x]);
b.add(y, a[x]);
ans -= b.sum(u, v);
pos[x] = y;
inv_pos[y] = x;
l[x] = u;
r[x] = v;
std::cout << ans << "\n";
}
}