結果
| 問題 |
No.3265 地元に帰れば天才扱い！
|
| コンテスト | |
| ユーザー |
 Sinonen
|
| 提出日時 | 2025-09-06 14:09:58 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 734 ms / 2,500 ms |
| コード長 | 6,379 bytes |
| コンパイル時間 | 3,528 ms |
| コンパイル使用メモリ | 290,880 KB |
| 実行使用メモリ | 26,612 KB |
| 最終ジャッジ日時 | 2025-09-06 14:10:41 |
| 合計ジャッジ時間 | 22,186 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 21 |
ソースコード
/*
class SegTree:
def __init__(self, op, e, n, v=None):
self._n = n
self._op = op
self._e = e
self._log = (n - 1).bit_length()
self._size = 1 << self._log
self._d = [self._e] * (2 * self._size)
if v is not None:
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, x):
assert 0 <= p < self._n
p += self._size
self._d[p] = x
for i in range(1, self._log + 1):
self._update(p >> i)
def get(self, p):
assert 0 <= p < self._n
return self._d[p + self._size]
def prod(self, l, r):
assert 0 <= l <= r <= self._n
sml, smr = self._e, self._e
l += self._size
r += self._size
while l < r:
if l & 1:
sml = self._op(sml, self._d[l])
l += 1
if r & 1:
r -= 1
smr = self._op(self._d[r], smr)
l >>= 1
r >>= 1
return self._op(sml, smr)
def all_prod(self):
return self._d[1]
def _update(self, k):
self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1])
#https://qiita.com/AkariLuminous/items/32cbf5bc3ffb2f84a898
def ADD(a, b):
return a + b
N, M = list(map(int,input().split()))
Data = []
for i in range(N):
a = list(map(int,input().split()))
a[1] -= 1
a[2] -= 1
a.append(i)
Data.append(a)
Count = SegTree(ADD, 0, M + 1)
Rate = SegTree(ADD, 0, M)
ans = 0
for i in range(N):
Rate.set(i, Data[i][0])
Count.set(Data[i][1], Count.get(Data[i][1]) + 1)
Count.set(Data[i][2] + 1, Count.get(Data[i][2] + 1) -1)
ans += Data[i][0] * (Data[i][2] - Data[i][1] + 1)
for i in range(N):
ans -= Rate.prod(Data[i][1], Data[i][2] + 1)
Q = int(input())
for _ in range(Q):
x, y, u, v = list(map(int,input().split()))
x -= 1
y -= 1
u -= 1
v -= 1
ans -= Data[x][0] * (Data[x][2] - Data[x][1] + 1)
p = Count.prod(0, Data[x][3] + 1)
ans += Data[x][0] * p
if Data[x][1] <= Data[x][3] <= Data[x][2]:
ans -= Data[x][0]
ans += Rate.prod(Data[x][1], Data[x][2] + 1)
Count.set(Data[x][1], Count.get(Data[x][1]) - 1)
Count.set(Data[x][2] + 1, Count.get(Data[x][2] + 1) + 1)
Rate.set(Data[x][3], 0)
Data[x][1] = u
Data[x][2] = v
Data[x][3] = y
ans += Data[x][0] * (Data[x][2] - Data[x][1] + 1)
Count.set(Data[x][1], Count.get(Data[x][1]) + 1)
Count.set(Data[x][2] + 1, Count.get(Data[x][2] + 1) - 1)
Rate.set(Data[x][3], Data[x][0])
p = Count.prod(0, Data[x][3] + 1)
ans -= Data[x][0] * p
if Data[x][1] <= Data[x][3] <= Data[x][2]:
ans += Data[x][0]
ans -= Rate.prod(Data[x][1], Data[x][2] + 1)
print(ans)
*/
#include <bits/stdc++.h>
using namespace std;
struct SegTree {
using F = function<long long(long long, long long)>;
int _n, _log, _size;
F _op;
long long _e;
vector<long long> _d;
SegTree(F op, long long e, int n, vector<long long> v = {}) {
_n = n;
_op = op;
_e = e;
_log = 0;
while ((1 << _log) < n) _log++;
_size = 1 << _log;
_d.assign(2 * _size, _e);
if (!v.empty()) {
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, long long x) {
assert(0 <= p && p < _n);
p += _size;
_d[p] = x;
for (int i = 1; i <= _log; i++) {
_update(p >> i);
}
}
long long get(int p) {
assert(0 <= p && p < _n);
return _d[p + _size];
}
long long prod(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
long long sml = _e, smr = _e;
l += _size;
r += _size;
while (l < r) {
if (l & 1) {
sml = _op(sml, _d[l]);
l++;
}
if (r & 1) {
r--;
smr = _op(_d[r], smr);
}
l >>= 1;
r >>= 1;
}
return _op(sml, smr);
}
long long all_prod() {
return _d[1];
}
private:
void _update(int k) {
_d[k] = _op(_d[2 * k], _d[2 * k + 1]);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
auto ADD = [](long long a, long long b) { return a + b; };
int N, M;
cin >> N >> M;
vector<vector<long long>> Data;
for (int i = 0; i < N; i++) {
vector<long long> a(3);
cin >> a[0] >> a[1] >> a[2];
a[1] -= 1;
a[2] -= 1;
a.push_back(i);
Data.push_back(a);
}
SegTree Count(ADD, 0, M + 1);
SegTree Rate(ADD, 0, M);
long long ans = 0;
for (int i = 0; i < N; i++) {
Rate.set(i, Data[i][0]);
Count.set(Data[i][1], Count.get(Data[i][1]) + 1);
Count.set(Data[i][2] + 1, Count.get(Data[i][2] + 1) - 1);
ans += Data[i][0] * (Data[i][2] - Data[i][1] + 1);
}
for (int i = 0; i < N; i++) {
ans -= Rate.prod(Data[i][1], Data[i][2] + 1);
}
int Q;
cin >> Q;
while (Q--) {
int x, y, u, v;
cin >> x >> y >> u >> v;
x--; y--; u--; v--;
ans -= Data[x][0] * (Data[x][2] - Data[x][1] + 1);
long long p = Count.prod(0, Data[x][3] + 1);
ans += Data[x][0] * p;
if (Data[x][1] <= Data[x][3] && Data[x][3] <= Data[x][2]) {
ans -= Data[x][0];
}
ans += Rate.prod(Data[x][1], Data[x][2] + 1);
Count.set(Data[x][1], Count.get(Data[x][1]) - 1);
Count.set(Data[x][2] + 1, Count.get(Data[x][2] + 1) + 1);
Rate.set(Data[x][3], 0);
Data[x][1] = u;
Data[x][2] = v;
Data[x][3] = y;
ans += Data[x][0] * (Data[x][2] - Data[x][1] + 1);
Count.set(Data[x][1], Count.get(Data[x][1]) + 1);
Count.set(Data[x][2] + 1, Count.get(Data[x][2] + 1) - 1);
Rate.set(Data[x][3], Data[x][0]);
p = Count.prod(0, Data[x][3] + 1);
ans -= Data[x][0] * p;
if (Data[x][1] <= Data[x][3] && Data[x][3] <= Data[x][2]) {
ans += Data[x][0];
}
ans -= Rate.prod(Data[x][1], Data[x][2] + 1);
cout << ans << "\n";
}
return 0;
}