oj.uz

Submission #512724

# Submission time Handle Problem Language Result Execution time Memory
512724 2022-01-16T17:11:28 Z kartel Sjeckanje (COCI21_sjeckanje) C++14
55 / 110
 39 ms 1944 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 = 1e5 + 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 1 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 1 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 12 ms 588 KB Output is correct
8 Correct 11 ms 664 KB Output is correct
9 Correct 10 ms 648 KB Output is correct
10 Correct 9 ms 588 KB Output is correct
11 Correct 10 ms 588 KB Output is correct
12 Correct 11 ms 588 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 12 ms 588 KB Output is correct
8 Correct 11 ms 664 KB Output is correct
9 Correct 10 ms 648 KB Output is correct
10 Correct 9 ms 588 KB Output is correct
11 Correct 10 ms 588 KB Output is correct
12 Correct 11 ms 588 KB Output is correct
13 Runtime error 39 ms 1944 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -