// https://oj.uz/problem/view/JOI22_sugar
#include <bits/stdc++.h>
using namespace std;
/*
Hall's theorem
Answer = A - max(|S| - |NG(S)|)
*/
const int64_t inf = 1e18;
class segtree_t {
public:
segtree_t *left, *right;
int l, r, m;
int64_t x[2][2], lazyx, lazy_mid, mid;
segtree_t(int l, int r) : l(l), r(r), m(l + r >> 1) {
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
x[i][j] = 0;
}
}
if (l == r) return;
left = new segtree_t(l, m);
right = new segtree_t(m + 1, r);
}
void Update(int s, int t, int64_t val) {
if (l > t || r < s) return;
if (s <= l && r <= t) {
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
x[i][j] += val;
}
}
lazyx += val;
lazy_mid += val;
mid += val;
return;
}
Down();
if (s <= m && m < t) mid += val;
left->Update(s, t, val);
right->Update(s, t, val);
Up();
}
void Down() {
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
left->x[i][j] += lazyx;
right->x[i][j] += lazyx;
}
}
left->lazy_mid += lazy_mid;
left->lazyx += lazyx;
left->mid += lazy_mid;
right->lazy_mid += lazy_mid;
right->lazyx += lazyx;
right->mid += lazy_mid;
lazy_mid = lazyx = 0;
}
void Up() {
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
x[i][j] = -inf;
for (int k = 0; k < 2; k++) {
x[i][j] = max<int64_t>(x[i][j], left->x[i][k] + right->x[k][j] - 1ll * k * mid);
}
}
}
for (int i = 0; i < 2; i++) {
x[i][0] = max(x[i][0], left->x[i][0]);
x[0][i] = max(x[0][i], right->x[0][i]);
}
}
};
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int q, L;
cin >> q >> L;
vector<int> t(q), a(q), x(q);
for (int i = 0; i < q; i++) cin >> t[i] >> x[i] >> a[i];
vector<int> cord;
for (int i = 0; i < q; i++) {
if (t[i] == 1) cord.emplace_back(x[i]);
}
sort(cord.begin(), cord.end());
cord.resize(unique(cord.begin(), cord.end()) - cord.begin());
int N = cord.size();
segtree_t* tree = new segtree_t(0, N);
int64_t A = 0;
for (int i = 0; i < q; i++) {
if (t[i] == 1) {
A += a[i];
int y = lower_bound(cord.begin(), cord.end(), x[i]) - cord.begin();
tree->Update(y, y, +a[i]);
} else {
int u = lower_bound(cord.begin(), cord.end(), x[i] - L) - cord.begin();
int v = upper_bound(cord.begin(), cord.end(), x[i] + L) - cord.begin() - 1;
tree->Update(u, v, -a[i]);
}
cout << A - max<int64_t>(0, tree->x[0][0]) << '\n';
}
}
Compilation message
sugar.cpp: In constructor 'segtree_t::segtree_t(int, int)':
sugar.cpp:21:51: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
21 | segtree_t(int l, int r) : l(l), r(r), m(l + r >> 1) {
| ~~^~~
| # |
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 |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
408 ms |
34560 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 |
Incorrect |
194 ms |
29056 KB |
Output isn't correct |
| 3 |
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 |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
