oj.uz

Submission #768968

# Submission time Handle Problem Language Result Execution time Memory
768968 2023-06-29T03:25:49 Z chanhchuong123 Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 391 ms 42172 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAX = 200200;
int n, q;
int a[MAX];

struct node {
    long long dp[2][2];
    int value[2];

    node(int _x = 0) {
        memset(dp, 0, sizeof dp); dp[1][1] = abs(_x);
        value[0] = value[1] = _x;
    }
};
node st[MAX << 2];

node merge(const node &u, const node &v) {
    node res;
    res.value[0] = u.value[0];
    res.value[1] = v.value[1];
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
            res.dp[i][j] = max(res.dp[i][j], u.dp[i][0] + v.dp[0][j]);
            res.dp[i][j] = max(res.dp[i][j], u.dp[i][0] + v.dp[1][j]);
            res.dp[i][j] = max(res.dp[i][j], u.dp[i][1] + v.dp[0][j]);
            if (1LL * u.value[1] * v.value[0] >= 0) res.dp[i][j] = max(res.dp[i][j], u.dp[i][1] + v.dp[1][j]);
        }
    }
    return res;
}

void build(int id, int l, int r) {
    if (l == r) st[id] = node(a[l]);
    else {
        int mid = l + r >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
        st[id] = merge(st[id << 1], st[id << 1 | 1]);
    }
}

void update(int id, int l, int r, int pos) {
    if (l == r) st[id] = node(a[l]);
    else {
        int mid = l + r >> 1;
        if (pos <= mid) update(id << 1, l, mid, pos);
        else update(id << 1 | 1, mid + 1, r, pos);
        st[id] = merge(st[id << 1], st[id << 1 | 1]);
    }
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);

    cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    for (int i = 1; i < n; ++i) {
        a[i] = a[i + 1] - a[i];
    }
    build(1, 1, n - 1);
    while (q--) {
        int l, r, x; cin >> l >> r >> x;
        a[r] -= x; if (r < n) update(1, 1, n - 1, r);
        if (l > 1) a[l - 1] += x, update(1, 1, n - 1, l - 1);
        cout << max({st[1].dp[0][0], st[1].dp[0][1], st[1].dp[1][0], st[1].dp[1][1]}) << '\n';
    }
	return 0;
}

Compilation message

Main.cpp: In function 'void build(int, int, int)':
Main.cpp:37:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In function 'void update(int, int, int, int)':
Main.cpp:47:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31572 KB Output is correct
2 Correct 12 ms 31676 KB Output is correct
3 Correct 12 ms 31676 KB Output is correct
4 Correct 12 ms 31672 KB Output is correct
5 Correct 12 ms 31620 KB Output is correct
6 Correct 12 ms 31612 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31572 KB Output is correct
2 Correct 12 ms 31676 KB Output is correct
3 Correct 12 ms 31676 KB Output is correct
4 Correct 12 ms 31672 KB Output is correct
5 Correct 12 ms 31620 KB Output is correct
6 Correct 12 ms 31612 KB Output is correct
7 Correct 15 ms 31776 KB Output is correct
8 Correct 16 ms 31768 KB Output is correct
9 Correct 15 ms 31740 KB Output is correct
10 Correct 16 ms 31680 KB Output is correct
11 Correct 15 ms 31752 KB Output is correct
12 Correct 15 ms 31716 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31572 KB Output is correct
2 Correct 12 ms 31676 KB Output is correct
3 Correct 12 ms 31676 KB Output is correct
4 Correct 12 ms 31672 KB Output is correct
5 Correct 12 ms 31620 KB Output is correct
6 Correct 12 ms 31612 KB Output is correct
7 Correct 15 ms 31776 KB Output is correct
8 Correct 16 ms 31768 KB Output is correct
9 Correct 15 ms 31740 KB Output is correct
10 Correct 16 ms 31680 KB Output is correct
11 Correct 15 ms 31752 KB Output is correct
12 Correct 15 ms 31716 KB Output is correct
13 Correct 339 ms 41488 KB Output is correct
14 Correct 391 ms 41576 KB Output is correct
15 Correct 326 ms 41556 KB Output is correct
16 Correct 345 ms 41436 KB Output is correct
17 Correct 323 ms 41320 KB Output is correct
18 Correct 330 ms 42172 KB Output is correct