oj.uz

Submission #934947

# Submission time Handle Problem Language Result Execution time Memory
934947 2024-02-28T08:34:50 Z MisterReaper Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 655 ms 49236 KB 
#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.0 / 15.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 6 ms 1116 KB Output is correct
8 Correct 6 ms 1116 KB Output is correct
9 Correct 6 ms 1116 KB Output is correct
10 Correct 6 ms 1116 KB Output is correct
11 Correct 6 ms 1136 KB Output is correct
12 Correct 6 ms 1116 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 6 ms 1116 KB Output is correct
8 Correct 6 ms 1116 KB Output is correct
9 Correct 6 ms 1116 KB Output is correct
10 Correct 6 ms 1116 KB Output is correct
11 Correct 6 ms 1136 KB Output is correct
12 Correct 6 ms 1116 KB Output is correct
13 Correct 609 ms 48588 KB Output is correct
14 Correct 637 ms 48560 KB Output is correct
15 Correct 641 ms 48504 KB Output is correct
16 Correct 618 ms 48596 KB Output is correct
17 Correct 655 ms 48580 KB Output is correct
18 Correct 543 ms 49236 KB Output is correct