#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];
xs.push_back(queries[i][1]);
xs.push_back(queries[i][1] + 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 ant = 0, sugar = 0, sugar2 = 0;
long long lazy_sugar = 0, lazy_sugar2 = 0;
vector<vector<long long>> mn = { { 0, 0 }, { 0, 0 } };
Node operator+(Node b) {
Node a = *this;
Node res;
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
res.mn[i][j] = INF;
res.mn[i][j] = min(res.mn[i][j], a.mn[i][0] + b.mn[0][j]);
res.mn[i][j] = min(res.mn[i][j], a.mn[i][0] + b.mn[1][j]);
res.mn[i][j] = min(res.mn[i][j], a.mn[i][1] + b.mn[0][j]);
res.mn[i][j] = min(res.mn[i][j], a.mn[i][1] + b.mn[1][j] - a.sugar2);
}
}
res.sugar2 = b.sugar2;
return res;
}
};
vector<Node> nodes(4 * C);
auto apply = [&](int idx, long long delta_sugar, long long delta_sugar2) {
nodes[idx].sugar += delta_sugar;
nodes[idx].sugar2 += delta_sugar2;
nodes[idx].lazy_sugar += delta_sugar;
nodes[idx].lazy_sugar2 += delta_sugar2;
nodes[idx].mn[0][0] = min(0LL, nodes[idx].mn[0][0] + delta_sugar);
nodes[idx].mn[0][1] += delta_sugar;
nodes[idx].mn[1][0] += delta_sugar;
nodes[idx].mn[1][1] += delta_sugar;
};
auto down = [&](int idx) {
apply(2 * idx + 1, nodes[idx].lazy_sugar, nodes[idx].lazy_sugar2);
apply(2 * idx + 2, nodes[idx].lazy_sugar, nodes[idx].lazy_sugar2);
nodes[idx].lazy_sugar = 0;
nodes[idx].lazy_sugar2 = 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) {
nodes[idx].ant += delta;
nodes[idx].mn[0][0] = 0;
nodes[idx].mn[0][1] = nodes[idx].mn[1][0] = INF;
nodes[idx].mn[1][1] = - nodes[idx].ant + nodes[idx].sugar;
} 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] = nodes[2 * idx + 1] + nodes[2 * idx + 2];
}
};
dfs(dfs, 0, 0, C);
};
auto addSugar = [&](int ql, int qr, long long delta_sugar, long long delta_sugar2) -> void {
ql = lower_bound(xs.begin(), xs.end(), ql) - xs.begin();
qr = lower_bound(xs.begin(), xs.end(), qr) - xs.begin();
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, delta_sugar2);
down(idx);
int m = (l + r) >> 1;
self(self, 2 * idx + 1, l, m);
self(self, 2 * idx + 2, m, r);
nodes[idx] = 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, 0);
addSugar(x - radius, x + radius, 0, +c);
}
cout << total + query() << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
3965 ms |
250940 KB |
Output is correct |
| 5 |
Correct |
1773 ms |
193296 KB |
Output is correct |
| 6 |
Execution timed out |
4059 ms |
295688 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
