oj.uz

Submission #985515

# Submission time Handle Problem Language Result Execution time Memory
985515 2024-05-18T02:59:34 Z blackavar Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 353 ms 55744 KB 
#include <bits/stdc++.h>
using namespace std;

long long n, a[1000005], d[1000005], q, dp[1000005];

struct Node{
    long long left = -1, right = -1, val = 0, missl = 0, missr = 0, missb = 0;
};

vector <Node> seg;

void sub1(long long l, long long r, long long x) {
    d[0] = d[1];
    for (int i = 1; i < n; i++) {
        if (d[i] * d[i - 1] > 0) dp[i] = dp[i - 1] + abs(d[i]);
        else dp[i] = max(dp[i - 1], dp[i - 2] + abs(d[i]));
    }
    cout << dp[n - 1] << "\n";
}

Node Merge(Node a, Node b) {
    Node c;
    c.left = a.left;
    c.right = b.right;
    if (a.right == b.left) {
        c.val = a.val + b.val;
        c.missr = a.val + b.missr;
        c.missl = a.missl + b.val;
        c.missb = a.missl + b.missr;
    }
    else {
        c.val = max(a.val + b.missl, a.missr + b.val);
        c.missl = max(a.missb + b.val, a.missl + b.missl);
        c.missr = max(a.missr + b.missr, a.val + b.missb);
        c.missb = max({a.missb + b.missb, a.missb + b.missr, a.missl + b.missb});
    }
    return c;
}

void build(long long id, long long l, long long r) {
    if (l == r) {
        Node temp;
        temp.left = temp.right = (d[l] >= 0);
        temp.val = abs(d[l]);
        seg[id] = temp;
        return;
    }
    long long mid = (l + r) / 2;
    build(2 * id, l, mid);
    build(2 * id + 1, mid + 1, r);
    seg[id] = Merge(seg[2 * id], seg[2 * id + 1]);
}

void update(long long id, long long l, long long r, long long pos) {
    if (l > pos || r < pos) return;
    if (l == r) {
        Node temp;
        temp.left = temp.right = (d[l] >= 0);
        temp.val = abs(d[l]);
        seg[id] = temp;
        return;
    }
    long long mid = (l + r) / 2;
    if (pos <= mid) update(2 * id, l, mid, pos);
    else update(2 * id + 1, mid + 1, r, pos);
    seg[id] = Merge(seg[2 * id], seg[2 * id + 1]);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> q;
    seg.resize(4 * n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i < n; i++) d[i] = a[i] - a[i + 1];
    dp[0] = 0;
    build(1, 1, n - 1);
    while (q--) {
        long long l, r, x;
        cin >> l >> r >> x;
        d[l - 1] -= x;
        d[r] += x;
        update(1, 1, n - 1, l - 1);
        update(1, 1, n - 1, r);
        cout << seg[1].val << "\n";
    }
    return 0;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4452 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 4 ms 4952 KB Output is correct
8 Correct 4 ms 4956 KB Output is correct
9 Correct 4 ms 4956 KB Output is correct
10 Correct 4 ms 4956 KB Output is correct
11 Correct 4 ms 4956 KB Output is correct
12 Correct 3 ms 5208 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4452 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 4 ms 4952 KB Output is correct
8 Correct 4 ms 4956 KB Output is correct
9 Correct 4 ms 4956 KB Output is correct
10 Correct 4 ms 4956 KB Output is correct
11 Correct 4 ms 4956 KB Output is correct
12 Correct 3 ms 5208 KB Output is correct
13 Correct 325 ms 52904 KB Output is correct
14 Correct 346 ms 55380 KB Output is correct
15 Correct 319 ms 55316 KB Output is correct
16 Correct 318 ms 55052 KB Output is correct
17 Correct 353 ms 55120 KB Output is correct
18 Correct 294 ms 55744 KB Output is correct