oj.uz

Submission #657829

# Submission time Handle Problem Language Result Execution time Memory
657829 2022-11-11T13:52:55 Z adaawf Sjeckanje (COCI21_sjeckanje) C++17
55 / 110
 31 ms 10588 KB 
#include <iostream>
using namespace std;
long long int a[200005], b[200005], t[200005][2][2];
void pull(int v, int l, int r) {
    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(int v, int l, int r) {
    if (l == r) {
        t[v][1][1] = abs(b[l]);
        return;
    }
    int mid = (l + r) / 2;
    init(v * 2, l, mid);
    init(v * 2 + 1, mid + 1, r);
    pull(v, l, r);
}
void update(int v, int l, int r, int x) {
    if (x < l || x > r) return;
    if (l == r) {
        t[v][1][1] = abs(b[l]);
        return;
    }
    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);
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (i >= 2) {
            b[i] = a[i] - a[i - 1];
        }
    }
    init(1, 2, n);
    for (int jj = 0; jj < q; jj++) {
        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 2 ms 340 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 328 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 2 ms 340 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 10 ms 860 KB Output is correct
8 Correct 7 ms 744 KB Output is correct
9 Correct 7 ms 724 KB Output is correct
10 Correct 7 ms 724 KB Output is correct
11 Correct 9 ms 728 KB Output is correct
12 Correct 7 ms 724 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 2 ms 340 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 10 ms 860 KB Output is correct
8 Correct 7 ms 744 KB Output is correct
9 Correct 7 ms 724 KB Output is correct
10 Correct 7 ms 724 KB Output is correct
11 Correct 9 ms 728 KB Output is correct
12 Correct 7 ms 724 KB Output is correct
13 Runtime error 31 ms 10588 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -