Submission #768968

#	Time	Username	Problem	Language	Result	Execution time	Memory
768968		chanhchuong123	Sjeckanje (COCI21_sjeckanje)	C++14	110 / 110	391 ms	42172 KiB

Main

#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 (stderr)

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 / 15
• Subtask 2: 40 / 40
• Subtask 3: 55 / 55