This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
template <class X, class Y>
bool cmax(X &a, const Y &b) {
return a < b ? a = b, 1 : 0;
}
using ll = long long;
#define il i * 2
#define ir i + 2 + 1
const int N = 1500005;
vector<int> val;
int lo, hi, t[N], x[N], a[N];
ll dp[N * 4][2][2];
ll tag1[N * 4], tag2[N * 4];
void apply(int i, ll v1, ll v2) {
dp[i][0][0] += v1 + v2;
dp[i][1][1] -= v1;
dp[i][0][1] += v2;
dp[i][1][0] += v2;
tag1[i] += v1;
tag2[i] += v2;
}
void push(int i) {
apply(il, tag1[i], tag2[i]);
apply(ir, tag1[i], tag2[i]);
tag1[i] = tag2[i] = 0;
}
void pull(int i) {
for (int x = 0; x < 2; x++)
for (int y = 0; y < 2; y++) {
dp[i][x][y] = -1e18;
for (int z = 0; z < 2; z++)
cmax(dp[i][x][y], dp[il][x][z] + dp[ir][z ^ 1][y]);
}
}
void add(int i, int l, int r, ll v1, ll v2) {
if (l >= lo && r <= hi)
return apply(i, v1, v2);
push(i);
int m = (l + r) / 2;
if (m >= lo) add(il, l, m, v1, v2);
if (m < hi) add(ir, m + 1, r, v1, v2);
pull(i);
}
void add(int l, int r, ll v1, ll v2) {
if (l > r) return;
lo = l; hi = r;
add(1, 1, val.size(), v1, v2);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int q, m; cin >> q >> m;
for (int i = 0; i < q; i++) {
cin >> t[i] >> x[i] >> a[i];
if (t[i] == 2) {
val.push_back(x[i] - m);
val.push_back(x[i] + m);
} else val.push_back(x[i]);
}
sort(val.begin(), val.end());
val.erase(unique(val.begin(), val.end()), val.end());
ll sum = 0;
for (int i = 0; i < q; i++) {
if (t[i] == 1) {
int l = upper_bound(val.begin(),
val.end(), x[i]) - val.begin();
add(l + 1, val.size(), a[i], 0);
add(l, l, 0, a[i]); sum += a[i];
} else {
int l = upper_bound(val.begin(),
val.end(), x[i] - m) - val.begin();
int r = upper_bound(val.begin(),
val.end(), x[i] + m) - val.begin();
add(r + 1, val.size(), -a[i], 0);
add(l, r, 0, -a[i]);
}
cout << sum - dp[1][0][1] << '\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |