oj.uz

Submission #512725

# Submission time Handle Problem Language Result Execution time Memory
512725 2022-01-16T17:11:45 Z kartel Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 814 ms 29644 KB 
#include <bits/stdc++.h>
#define blue 0
#define red 1
#define purple 2
#define pb push_back
#define F first
#define S second
#define sz(x) (int)x.size()
#define el "\n"
using namespace std;
typedef long long ll;

const int N = 2e5 + 500;

ll a[N], f[N][2], b[N];
ll t[4 * N][2][2];
int n, q;

int sg(ll x) {
    if (x < 0) {
        return -1;
    }
    if (x > 0) {
        return 1;
    }
    return 0;
}

void comb(int v, int vl, int vr, int md) {
    t[v][0][0] = max({t[vl][0][0] + t[vr][0][0], t[vl][0][0] + t[vr][1][0], t[vl][0][1] + t[vr][0][0]});
    t[v][0][1] = max({t[vl][0][0] + t[vr][0][1], t[vl][0][0] + t[vr][1][1], t[vl][0][1] + t[vr][0][1]});
    t[v][1][0] = max({t[vl][1][0] + t[vr][0][0], t[vl][1][0] + t[vr][1][0], t[vl][1][1] + t[vr][0][0]});
    t[v][1][1] = max({t[vl][1][0] + t[vr][0][1], t[vl][1][0] + t[vr][1][1], t[vl][1][1] + t[vr][0][1]});
    if (sg(b[md]) == sg(b[md + 1])) {
        t[v][0][0] = max(t[v][0][0], t[vl][0][1] + t[vr][1][0]);
        t[v][0][1] = max(t[v][0][1], t[vl][0][1] + t[vr][1][1]);
        t[v][1][0] = max(t[v][1][0], t[vl][1][1] + t[vr][1][0]);
        t[v][1][1] = max(t[v][1][1], t[vl][1][1] + t[vr][1][1]);
    }
}

void build(int v, int l, int r) {
    if (l == r) {
        t[v][0][0] = 0;
        t[v][0][1] = -1e18;
        t[v][1][0] = -1e18;
        t[v][1][1] = abs(b[l]);
    } else {
        int md = (l + r) >> 1;
        build(v * 2, l, md);
        build(v * 2 + 1, md + 1, r);
        comb(v, v * 2, v * 2 + 1, md);
    }
}

void upd(int v, int l, int r, int ps, int val) {
    if (l == r) {
        b[l] += val;
        t[v][1][1] = abs(b[l]);
    } else {
        int md = (l + r) >> 1;
        if (ps <= md) {
            upd(v * 2, l, md, ps, val);
        } else {
            upd(v * 2 + 1, md + 1, r, ps, val);
        }
        comb(v, v * 2, v * 2 + 1, md);
    }
}

int main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i < n; i++) {
        b[i] = a[i + 1] - a[i];
    }
    build(1, 1, n - 1);
    while (q--) {
        int l, r, x;
        cin >> l >> r >> x;
        if (l - 1 >= 1) {
            upd(1, 1, n - 1, l - 1, +x);
        }
        if (r < n) {
            upd(1, 1, n - 1, r, -x);
        }
        cout << max({t[1][0][0], t[1][0][1], t[1][1][0], t[1][1][1]}) << el;
//        for (int i = 1; i <= n; i++) {
//            for (int j = 0; j < 2; j++) {
//                f[i][j] = -1e18;
//            }
//        }
//        f[1][0] = 0;
//        f[1][1] = abs(b[1]);
//        for (int i = 2; i < n; i++) {
//            if ((b[i - 1] < 0 && b[i] < 0) || (b[i - 1] > 0 && b[i] > 0)) {
//                f[i][1] = max(f[i][1], f[i - 1][1] + abs(b[i]));
//            }
//            f[i][1] = max(f[i - 1][0] + abs(b[i]), f[i][1]);
//            f[i][0] = max(f[i - 1][0], f[i - 1][1]);
//        }
//        cout << max(f[n - 1][0], f[n - 1][1]) << el;
    }
}

Subtask #1
15.0 / 15.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 9 ms 588 KB Output is correct
8 Correct 10 ms 588 KB Output is correct
9 Correct 10 ms 588 KB Output is correct
10 Correct 9 ms 656 KB Output is correct
11 Correct 10 ms 656 KB Output is correct
12 Correct 9 ms 640 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 9 ms 588 KB Output is correct
8 Correct 10 ms 588 KB Output is correct
9 Correct 10 ms 588 KB Output is correct
10 Correct 9 ms 656 KB Output is correct
11 Correct 10 ms 656 KB Output is correct
12 Correct 9 ms 640 KB Output is correct
13 Correct 814 ms 27796 KB Output is correct
14 Correct 778 ms 28960 KB Output is correct
15 Correct 776 ms 28888 KB Output is correct
16 Correct 790 ms 28888 KB Output is correct
17 Correct 795 ms 28884 KB Output is correct
18 Correct 763 ms 29644 KB Output is correct