Submission #1094962

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094962		manhlinh1501	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	329 ms	33048 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
const int MAXN = 3e5 + 5;
const i64 oo64 = 1e18 + 5;

struct event {
    int l, r, x;
    event(int l = 0, int r = 0, int x = 0) : l(l), r(r), x(x) {}
};

const int INC = 0;
const int DEC = 1;

int N, Q;
i64 a[MAXN];
event query[MAXN];

namespace subtask1 {
    const int MAXN = 3e3 + 5;
    i64 dp[MAXN][2];

    void solve() {
        memset(dp, -0x3f, sizeof dp);
        dp[0][INC] = dp[0][DEC] = 0;
        dp[1][INC] = dp[1][DEC] = 0;
        for(int i = 2; i <= N; i++) {
            dp[i][INC] = dp[i][DEC] = max(dp[i - 1][INC], dp[i - 1][DEC]);

            if(a[i] > 0)
                dp[i][INC] = max(dp[i][INC], max(dp[i - 1][INC], dp[i - 2][DEC]) + a[i]);
            if(a[i] < 0)
                dp[i][DEC] = max(dp[i][DEC], max(dp[i - 1][DEC], dp[i - 2][INC]) - a[i]);
        }

        cout << max(dp[N][INC], dp[N][DEC]) << "\n";
    }

    void solution() {
        for(int i = 1; i <= Q; i++) {
            const auto [l, r, x] = query[i];
            a[l] += x;
            a[r + 1] -= x;
            solve();
        }
    }
}

namespace solver {
    namespace ST {
        int N;
        i64 tree[MAXN * 4][2][2];
        i64 b[MAXN];

        void init(int _N) {
            N = _N;
        }

        void update(int id, int l, int r, int p, int x) {
            if(r < p or l > p) return;
            if(l == r) {
                b[p] += x;
                tree[id][1][1] = abs(b[p]);
                tree[id][0][0] = 0;
                return;
            }

            int m = (l + r) / 2;
            if(p <= m)
                update(id * 2, l, m, p, x);
            else
                update(id * 2 + 1, m + 1, r, p, x);

            for(int x = 0; x < 2; x++) {
                for(int y = 0; y < 2; y++) {
                    tree[id][x][y] = tree[id * 2][x][0] + tree[id * 2 + 1][0][y];
                }
            }

            for(int x = 0; x < 2; x++) {
                for(int y = 0; y < 2; y++) {
                    for(int z = 0; z < 2; z++)
                        tree[id][x][y] = max(tree[id][x][y], tree[id * 2][x][z] + tree[id * 2 + 1][z ^ 1][y]);
                }
            }

            if(b[m] * b[m + 1] > 0) {
                for(int x = 0; x < 2; x++) {
                    for(int y = 0; y < 2; y++)
                        tree[id][x][y] = max(tree[id][0][0], tree[id * 2][x][1] + tree[id * 2 + 1][1][y]);
                }
            }
        }

        void update(int p, int x) {
            return update(1, 1, N - 1, p, x);
        }

        i64 get() {
            i64 ans = 0;

            for(int x = 0; x < 2; x++) {
                for(int y = 0; y < 2; y++)
                    ans = max(ans, tree[1][x][y]);
            }

            return ans;
        }
    }

    void solution() {
        ST::init(N);

        for(int i = 1; i < N; i++) ST::update(i, a[i + 1] - a[i]);

        for(int i = 1; i <= Q; i++) {
            const auto [l, r, x] = query[i];
            ST::update(l - 1, x);
            ST::update(r, -x);
            cout << ST::get() << "\n";
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> Q;

    for(int i = 1; i <= N; i++) cin >> a[i];

    for(int i = 1; i <= Q; i++) {
        auto &[l, r, x] = query[i];
        cin >> l >> r >> x;
    }
    solver::solution();
}

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