#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q, radius;
cin >> q >> radius;
vector<array<int, 3>> queries(q);
vector<int> xs;
for (int i = 0; i < q; i++) {
cin >> queries[i][0] >> queries[i][1] >> queries[i][2];
if (queries[i][0] == 1) {
xs.push_back(queries[i][1]);
}
}
sort(xs.begin(), xs.end());
xs.resize(unique(xs.begin(), xs.end()) - xs.begin());
int C = xs.size();
const long long INF = 1e18;
struct Node {
long long sugar = 0, lazy_sugar = 0;
vector<vector<long long>> mn = { { 0, 0 }, { 0, 0 } };
void merge(Node a, Node b) {
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
mn[i][j] = INF;
mn[i][j] = min(mn[i][j], a.mn[i][0] + b.mn[0][j]);
mn[i][j] = min(mn[i][j], a.mn[i][0] + b.mn[1][j]);
mn[i][j] = min(mn[i][j], a.mn[i][1] + b.mn[0][j]);
mn[i][j] = min(mn[i][j], a.mn[i][1] + b.mn[1][j] - sugar);
mn[i][0] = min(mn[i][0], a.mn[i][j]);
mn[0][j] = min(mn[0][j], b.mn[i][j]);
}
}
}
};
vector<Node> nodes(4 * C);
auto apply = [&](int idx, long long delta_sugar) -> void {
nodes[idx].sugar += delta_sugar;
nodes[idx].lazy_sugar += delta_sugar;
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
nodes[idx].mn[i][j] += delta_sugar;
}
}
};
auto down = [&](int idx) -> void {
if (nodes[idx].lazy_sugar == 0) return;
apply(2 * idx + 1, nodes[idx].lazy_sugar);
apply(2 * idx + 2, nodes[idx].lazy_sugar);
nodes[idx].lazy_sugar = 0;
};
auto addAnt = [&](int x, int delta) -> void {
x = lower_bound(xs.begin(), xs.end(), x) - xs.begin();
auto dfs = [&](auto self, int idx, int l, int r) -> void {
if (l + 1 == r) {
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
nodes[idx].mn[i][j] -= delta;
}
}
} else {
down(idx);
int m = (l + r) >> 1;
if (x < m) self(self, 2 * idx + 1, l, m);
else self(self, 2 * idx + 2, m, r);
nodes[idx].merge(nodes[2 * idx + 1], nodes[2 * idx + 2]);
}
};
dfs(dfs, 0, 0, C);
};
auto addSugar = [&](int ql, int qr, long long delta_sugar) -> void {
ql = lower_bound(xs.begin(), xs.end(), ql) - xs.begin();
qr = lower_bound(xs.begin(), xs.end(), qr) - xs.begin();
if (ql == qr) return;
auto dfs = [&](auto self, int idx, int l, int r) -> void {
if (r <= ql || qr <= l) return;
if (ql <= l && r <= qr) return apply(idx, delta_sugar);
down(idx);
int m = (l + r) >> 1;
self(self, 2 * idx + 1, l, m);
self(self, 2 * idx + 2, m, r);
if (ql <= m - 11 && m + 1 <= r) nodes[idx].sugar += delta_sugar;
nodes[idx].merge(nodes[2 * idx + 1], nodes[2 * idx + 2]);
};
dfs(dfs, 0, 0, C);
};
auto query = [&]() -> long long {
long long res = INF;
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
res = min(res, nodes[0].mn[i][j]);
}
}
return res;
};
long long total = 0;
for (auto [type, x, c] : queries) {
if (type == 1) {
addAnt(x, +c);
total += c;
}
if (type == 2) {
addSugar(x - radius, x + radius + 1, +c);
}
cout << total + min(0LL, query()) << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
596 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
