oj.uz

Submission #1094962

# Submission time Handle Problem Language Result Execution time Memory
1094962 2024-10-01T03:47:47 Z manhlinh1501 Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 329 ms 33048 KB 
#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.0 / 15.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3928 KB Output is correct
2 Correct 2 ms 3932 KB Output is correct
3 Correct 2 ms 3932 KB Output is correct
4 Correct 2 ms 3932 KB Output is correct
5 Correct 2 ms 3932 KB Output is correct
6 Correct 3 ms 3892 KB Output is correct
7 Correct 5 ms 4440 KB Output is correct
8 Correct 5 ms 4184 KB Output is correct
9 Correct 5 ms 4188 KB Output is correct
10 Correct 5 ms 4268 KB Output is correct
11 Correct 4 ms 4188 KB Output is correct
12 Correct 5 ms 4356 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3928 KB Output is correct
2 Correct 2 ms 3932 KB Output is correct
3 Correct 2 ms 3932 KB Output is correct
4 Correct 2 ms 3932 KB Output is correct
5 Correct 2 ms 3932 KB Output is correct
6 Correct 3 ms 3892 KB Output is correct
7 Correct 5 ms 4440 KB Output is correct
8 Correct 5 ms 4184 KB Output is correct
9 Correct 5 ms 4188 KB Output is correct
10 Correct 5 ms 4268 KB Output is correct
11 Correct 4 ms 4188 KB Output is correct
12 Correct 5 ms 4356 KB Output is correct
13 Correct 329 ms 32440 KB Output is correct
14 Correct 311 ms 32544 KB Output is correct
15 Correct 317 ms 32596 KB Output is correct
16 Correct 304 ms 32596 KB Output is correct
17 Correct 301 ms 32340 KB Output is correct
18 Correct 273 ms 33048 KB Output is correct