Submission #378462

#	Time	Username	Problem	Language	Result	Execution time	Memory
378462		cuom1999	Sjeckanje (COCI21_sjeckanje)	C++14	110 / 110	1066 ms	48664 KiB

Main

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

int a[200005];

int sgn(long long x) {
    if (x > 0) return 1;
    if (x < 0) return -1;
    return 0;
}

struct IT {
    struct Node {
        long long value[2][2] = {0};
        long long lValue, rValue;
    };
    vector<Node> st;
    IT(int n) {
        st.resize(4 * n);
    }

    Node combine(Node a, Node b) {
        Node res;
        for (int i = 0; i <= 1; i++) {
            for (int j = 0; j <= 1; j++) {
                for (int k = 0; k <= 1; k++) {
                    for (int k1 = 0; k1 <= 1; k1++) {
                        int sign = sgn(a.rValue) * sgn(b.lValue);
                        if (k == 1 && k1 == 1 && sign == -1) continue; 
                        res.value[i][j] = max(res.value[i][j], a.value[i][k] + b.value[k1][j]);
                    }
                }
            }
        }
        res.lValue = a.lValue;
        res.rValue = b.rValue;
        return res;
    }

    void build(int id, int l, int r) {
        if (l == r) {
            st[id].value[1][1] = abs(a[l + 1] - a[l]);
            st[id].lValue = st[id].rValue = a[l + 1] - a[l];
            return;
        }
        int mid = (l + r) / 2;
        build(id * 2, l, mid);
        build(id * 2 + 1, mid + 1, r);
        st[id] = combine(st[id * 2], st[id * 2 + 1]);
        // cout << id << " " << st[id].value[1][0] << endl;
    }

    void update(int id, int l, int r, int u, long long v) {
        if (l == r) {
            long long val = st[id].lValue + v;
            st[id].lValue = st[id].rValue = val;
            st[id].value[1][1] = abs(val);
            // cout << l << " " << val << endl;
            return;
        }
        int mid = (l + r) / 2;
        if (u <= mid) update(id * 2, l, mid, u, v);
        else update(id * 2 + 1, mid + 1, r, u, v);
        st[id] = combine(st[id * 2], st[id * 2 + 1]);
    }
    long long getValue(int id) {
        long long res = 0;
        for (int i = 0; i <= 1; i++) {
            for (int j = 0; j <= 1; j++) {
                res = max(res, st[id].value[i][j]);
            }
        }
        return res;
    } 
};

int main() {
    // freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(NULL);

    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    IT seg(n);
    seg.build(1, 1, n - 1);

    // cout << seg.getValue(1) << endl;
    // return 0;
    for (int z = 1; z <= q; z++) {
        int l, r, x;
        cin >> l >> r >> x;
        l--;
        if (l > 0) seg.update(1, 1, n - 1, l, x);
        if (r < n) seg.update(1, 1, n - 1, r, -x);
        cout << seg.getValue(1) << "\n";
    }


    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 40 / 40
• Subtask 3: 55 / 55