Submission #1150366

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150366		antonn	Ants and Sugar (JOI22_sugar)	C++20	6 / 100	4093 ms	18828 KiB

sugar

#include <bits/stdc++.h>
 
using namespace std;

typedef long long ll;

const int Q = 5e5 + 7;

ll c[Q], d[Q], sum;
int n;

ll get() {
    ll ans = 0, mx0 = -1e18, mx1 = 0;
    for (int i = 0; i < n; ++i) {
        ll c0 = mx0, c1 = mx1;
        mx0 = max(mx0, c1 - c[i]);
        mx1 = max(mx1, c0 + d[i]);
        ans = max(ans, mx1);
    }
    return sum - ans;
}

int main() {
    ios::sync_with_stdio(false); 
    cin.tie(0);
    int q, l; 
    cin >> q >> l;
    vector<ll> t(q + 1), x(q + 1), a(q + 1);
    for (int i = 1; i <= q; ++i) {
        cin >> t[i] >> x[i] >> a[i];
    } 
    vector<int> vals;
    vals.push_back(-2e9);
    for (int i = 1; i <= q; ++i) {
        vals.push_back(x[i]);
        vals.push_back(x[i] - l);
        vals.push_back(x[i] + l);
    }
    sort(vals.begin(), vals.end());
    vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
    n = vals.size();
    for (int i = 1; i <= q; ++i) {
        if (t[i] == 1) {
            int pos = lower_bound(vals.begin(), vals.end(), x[i]) - vals.begin();
            for (int j = pos; j < n; ++j) {
                c[j] += a[i];
                d[j] += a[i];
            }
            sum += a[i];
        } else {
            int pos = lower_bound(vals.begin(), vals.end(), x[i] + l) - vals.begin();
            for (int j = pos; j < n; ++j) {
                c[j] -= a[i];
            }
            pos = lower_bound(vals.begin(), vals.end(), x[i] - l) - vals.begin();
            for (int j = pos; j < n; ++j) {
                d[j] -= a[i];
            }
        }
        cout << get() << "\n";
    }
    return 0;
}

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