oj.uz

Submission #1044841

# Submission time Handle Problem Language Result Execution time Memory
1044841 2024-08-05T14:05:37 Z GasmaskChan Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 255 ms 26580 KB 
#include <bits/stdc++.h>

using namespace std;
#define int long long

const int MAX = 2e5 + 5;

int d[MAX];
struct SMT {
    struct Node {
        int f[2][2];
        Node() {
            memset(f, 0, sizeof f);
        }
    };

    int n;
    vector<Node> ST;

    SMT(int _n) {
        n = _n;
        int sz = __lg(n) + 2;
        ST.resize(1 << sz);
    }

    void update(int id, int l, int r, const int &pos) {
        if (pos < l || r < pos) return;
        if (l == r) {
            ST[id].f[1][1] = abs(d[l]);
            return;
        }
        int mid = (l + r) >> 1;
        update(id << 1, l, mid, pos);
        update(id << 1 | 1, mid + 1, r, pos);

        if ((d[mid] <= 0 && d[mid + 1] <= 0) || (d[mid] >= 0 && d[mid + 1] >= 0)) {
            ST[id].f[0][0] = max(ST[id << 1].f[0][1], ST[id << 1].f[0][0]) +
                             max(ST[id << 1 | 1].f[0][0], ST[id << 1 | 1].f[1][0]);
            ST[id].f[0][1] = max(ST[id << 1].f[0][0], ST[id << 1].f[0][1]) +
                             max(ST[id << 1 | 1].f[0][1], ST[id << 1 | 1].f[1][1]);
            ST[id].f[1][0] = max(ST[id << 1].f[1][0], ST[id << 1].f[1][1]) +
                             max(ST[id << 1 | 1].f[1][0], ST[id << 1 | 1].f[0][0]);
            ST[id].f[1][1] = max(ST[id << 1].f[1][0], ST[id << 1].f[1][1]) +
                             max(ST[id << 1 | 1].f[1][1], ST[id << 1 | 1].f[0][1]);
        }
        else {
            ST[id].f[0][0] = max(ST[id << 1].f[0][1] + ST[id << 1 | 1].f[0][0],
                                 ST[id << 1].f[0][0] + ST[id << 1 | 1].f[1][0]);
            ST[id].f[0][1] = max(ST[id << 1].f[0][0] + ST[id << 1 | 1].f[1][1],
                                 ST[id << 1].f[0][1] + ST[id << 1 | 1].f[0][1]);
            ST[id].f[1][0] = max(ST[id << 1].f[1][1] + ST[id << 1 | 1].f[0][0],
                                 ST[id << 1].f[1][0] + ST[id << 1 | 1].f[1][0]);
            ST[id].f[1][1] = max(ST[id << 1].f[1][1] + ST[id << 1 | 1].f[0][1],
                                 ST[id << 1].f[1][0] + ST[id << 1 | 1].f[1][1]);
        }
    }

    void update(const int &pos) {
        update(1, 1, n, pos);
    }

    int get() {
        return max({ST[1].f[0][0], ST[1].f[1][0], ST[1].f[0][1], ST[1].f[1][1]});
    }
};

int a[MAX];
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout);
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    SMT sech(n - 1);
    for (int i = 1; i < n; i++) {
        d[i] = a[i + 1] - a[i];
        sech.update(i);
    }

    while (q--) {
        int l, r, x;
        cin >> l >> r >> x;
        d[l - 1] += x;
        d[r] -= x;
        if (l > 0) sech.update(l - 1);
        if (r < n) sech.update(r);
        cout << sech.get() << '\n';
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 3 ms 2908 KB Output is correct
8 Correct 4 ms 2908 KB Output is correct
9 Correct 3 ms 2908 KB Output is correct
10 Correct 3 ms 2904 KB Output is correct
11 Correct 4 ms 2908 KB Output is correct
12 Correct 3 ms 2908 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 3 ms 2908 KB Output is correct
8 Correct 4 ms 2908 KB Output is correct
9 Correct 3 ms 2908 KB Output is correct
10 Correct 3 ms 2904 KB Output is correct
11 Correct 4 ms 2908 KB Output is correct
12 Correct 3 ms 2908 KB Output is correct
13 Correct 237 ms 26120 KB Output is correct
14 Correct 249 ms 26080 KB Output is correct
15 Correct 245 ms 26140 KB Output is correct
16 Correct 255 ms 26216 KB Output is correct
17 Correct 237 ms 26160 KB Output is correct
18 Correct 214 ms 26580 KB Output is correct