Submission #934947

#	Time	Username	Problem	Language	Result	Execution time	Memory
934947		MisterReaper	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	655 ms	49236 KiB

Main

#include <bits/stdc++.h>
using i64 = long long;

struct Info {
    i64 bound[2];
    i64 dp[2][2];
    Info() { *this = Info(0); }
    Info(i64 x) {
        bound[0] = bound[1] = x;
        dp[0][0] = dp[0][1] = dp[1][0] = 0;
        dp[1][1] = std::abs(x);
    }
};

Info operator+(Info lhs, Info rhs) {
    Info res;
    res.bound[0] = lhs.bound[0];
    res.bound[1] = rhs.bound[1];
    for(int l = 0; l < 2; l++) {
        for(int r = 0; r < 2; r++) {
            for(int o = 0; o < 2; o++) {
                for(int m = 0; m < 2; m++) {
                    if(o && m) {
                        if((lhs.bound[1] < 0) == (rhs.bound[0] < 0)) {
                            res.dp[l][r] = std::max(res.dp[l][r], lhs.dp[l][o] + rhs.dp[m][r]);
                        }
                    } else {
                        res.dp[l][r] = std::max(res.dp[l][r], lhs.dp[l][o] + rhs.dp[m][r]);
                    }
                }
            }
        }
    }
    return res;
}

template<typename T>
struct SegTree {
    int n;
    std::vector<T> tree;
    SegTree(int n) : n(n) {
        tree.resize(4 * n);
    }

    void set(int node, int l, int r, int p, T v) {
        if(l == r) {
            tree[node] = v;
            return;
        }

        int mid = (l + r) / 2;
        if(p <= mid) {
            set(node * 2, l, mid, p, v);
        } else {
            set(node * 2 + 1, mid + 1, r, p, v);
        }
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }

    void set(int p, T v) {
        set(1, 0, n - 1, p, v);
    }

    T query(int node, int l, int r, int ql, int qr) {
        if(ql <= l && r <= qr) {
            return tree[node];
        }

        int mid = (l + r) / 2;
        if(qr <= mid) {
            return query(node * 2, l, mid, ql, qr);
        } else if(mid + 1 <= ql) {
            return query(node * 2 + 1, mid + 1, r, ql, qr);
        }
        return query(node * 2, l, mid, ql, qr) + query(node * 2 + 1, mid + 1, r, ql, qr);
    }

    T query(int l, int r) {
        return query(1, 0, n - 1, l, r);
    }
};

void solve() {
    int n, q;
    std::cin >> n >> q;

    std::vector<int> a(n);
    for(int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    std::vector<int> d(n - 1);
    for(int i = 1; i < n; i++) {
        d[i - 1] = a[i] - a[i - 1];
    }

    SegTree<Info> st(n - 1);
    for(int i = 0; i < n - 1; i++) {
        st.set(i, Info(d[i]));
    }

    for(int _ = 0; _ < q; _++) {
        int l, r, x;
        std::cin >> l >> r >> x;
        l--; r--;
        if(0 <= l - 1) {
            d[l - 1] += x;
            st.set(l - 1, Info(d[l - 1]));
        }
        if(r < n - 1) {
            d[r] -= x;
            st.set(r, Info(d[r]));
        }

        Info res = st.query(0, n - 2);
        i64 ans = 0;
        for(int i = 0; i < 2; i++) {
            for(int j = 0; j < 2; j++) {
                ans = std::max(ans, res.dp[i][j]);
            }
        }
        std::cout << ans << "\n";
    }
    
    return;
}

signed main() {
    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif

    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL); std::cout.tie(NULL);

    int t = 1; //std::cin >> t;
    for(int i = 1; i <= t; i++) {
        solve();
    }

    return 0;
}

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