oj.uz

Submission #561537

# Submission time Handle Problem Language Result Execution time Memory
561537 2022-05-13T05:55:50 Z two_sides Ants and Sugar (JOI22_sugar) C++17
0 / 100
 1 ms 340 KB 
#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';
    }
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 264 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -