oj.uz

Submission #657830

# Submission time Handle Problem Language Result Execution time Memory
657830 2022-11-11T13:53:28 Z adaawf Sjeckanje (COCI21_sjeckanje) C++17
55 / 110
 24 ms 9256 KB 
#include <iostream>
using namespace std;
long long int a[200005], b[200005], t[200005][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 692 KB Output is correct
8 Correct 7 ms 596 KB Output is correct
9 Correct 8 ms 672 KB Output is correct
10 Correct 6 ms 680 KB Output is correct
11 Correct 7 ms 596 KB Output is correct
12 Correct 8 ms 692 KB Output is correct

Subtask #3
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 692 KB Output is correct
8 Correct 7 ms 596 KB Output is correct
9 Correct 8 ms 672 KB Output is correct
10 Correct 6 ms 680 KB Output is correct
11 Correct 7 ms 596 KB Output is correct
12 Correct 8 ms 692 KB Output is correct
13 Runtime error 24 ms 9256 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -