oj.uz

Submission #657832

# Submission time Handle Problem Language Result Execution time Memory
657832 2022-11-11T13:56:00 Z adaawf Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 606 ms 25224 KB 
#include <iostream>
using namespace std;
long long int a[200005], b[200005], t[800005][2][2];
void pull(long long int v, long long int l, long long int r) {
    long long int mid = (l + r) / 2;
    t[v][1][1] = max(t[v * 2][1][0] + t[v * 2 + 1][1][1], max(t[v * 2][1][0] + t[v * 2 + 1][0][1], t[v * 2][1][1] + t[v * 2 + 1][0][1]));
    t[v][0][1] = max(t[v * 2][0][0] + t[v * 2 + 1][1][1], max(t[v * 2][0][0] + t[v * 2 + 1][0][1], t[v * 2][0][1] + t[v * 2 + 1][0][1]));
    t[v][1][0] = max(t[v * 2][1][0] + t[v * 2 + 1][1][0], max(t[v * 2][1][0] + t[v * 2 + 1][0][0], t[v * 2][1][1] + t[v * 2 + 1][0][0]));
    t[v][0][0] = max(t[v * 2][0][0] + t[v * 2 + 1][1][0], max(t[v * 2][0][0] + t[v * 2 + 1][0][0], t[v * 2][0][1] + t[v * 2 + 1][0][0]));
    if ((b[mid] >= 0 && b[mid + 1] >= 0) || (b[mid] <= 0 && b[mid + 1] <= 0)) {
        t[v][1][1] = max(t[v][1][1], t[v * 2][1][1] + t[v * 2 + 1][1][1]);
        t[v][0][1] = max(t[v][0][1], t[v * 2][0][1] + t[v * 2 + 1][1][1]);
        t[v][1][0] = max(t[v][1][0], t[v * 2][1][1] + t[v * 2 + 1][1][0]);
        t[v][0][0] = max(t[v][0][0], t[v * 2][0][1] + t[v * 2 + 1][1][0]);
    }
}
void init(long long int v, long long int l, long long int r) {
    if (l == r) {
        t[v][1][1] = abs(b[l]);
        return;
    }
    long long int mid = (l + r) / 2;
    init(v * 2, l, mid);
    init(v * 2 + 1, mid + 1, r);
    pull(v, l, r);
}
void update(long long int v, long long int l, long long int r, long long int x) {
    if (x < l || x > r) return;
    if (l == r) {
        t[v][1][1] = abs(b[l]);
        return;
    }
    long long int mid = (l + r) / 2;
    update(v * 2, l, mid, x);
    update(v * 2 + 1, mid + 1, r, x);
    pull(v, l, r);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    long long int n, q;
    cin >> n >> q;
    for (long long int i = 1; i <= n; i++) {
        cin >> a[i];
        if (i >= 2) {
            b[i] = a[i] - a[i - 1];
        }
    }
    init(1, 2, n);
    for (long long int jj = 0; jj < q; jj++) {
        long long int x, y, z;
        cin >> x >> y >> z;
        if (x > 1) {
            b[x] += z;
            update(1, 2, n, x);
        }
        if (y < n) {
            b[y + 1] -= z;
            update(1, 2, n, y + 1);
        }
        cout << max(t[1][1][1], max(t[1][0][1], max(t[1][1][0], t[1][0][0]))) << endl;
    }
}

Subtask #1
15.0 / 15.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 7 ms 596 KB Output is correct
8 Correct 6 ms 684 KB Output is correct
9 Correct 7 ms 596 KB Output is correct
10 Correct 7 ms 596 KB Output is correct
11 Correct 8 ms 664 KB Output is correct
12 Correct 9 ms 692 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 7 ms 596 KB Output is correct
8 Correct 6 ms 684 KB Output is correct
9 Correct 7 ms 596 KB Output is correct
10 Correct 7 ms 596 KB Output is correct
11 Correct 8 ms 664 KB Output is correct
12 Correct 9 ms 692 KB Output is correct
13 Correct 606 ms 23656 KB Output is correct
14 Correct 574 ms 25036 KB Output is correct
15 Correct 586 ms 25108 KB Output is correct
16 Correct 575 ms 25148 KB Output is correct
17 Correct 587 ms 24908 KB Output is correct
18 Correct 552 ms 25224 KB Output is correct