Submission #561596

#	Time	Username	Problem	Language	Result	Execution time	Memory
561596		two_sides	Ants and Sugar (JOI22_sugar)	C++17	100 / 100	1675 ms	126072 KiB

sugar

#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 build(int i, int l, int r) {
    dp[i][0][1] = -1e18;
    if (l < r) {
        int m = (l + r) / 2;
        build(il, l, m);
        build(ir, m + 1, r);
    }
}

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] = max(dp[il][x][y], dp[ir][x][y]);
            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());
    build(1, 1, val.size());
    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 - max(dp[1][1][0], 0ll) << '\n';
    }
}

• Subtask 1: 6 / 6
• Subtask 2: 16 / 16
• Subtask 3: 26 / 26
• Subtask 4: 52 / 52