Submission #1098594

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098594		duytuandao21	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	383 ms	29520 KiB

Main

#include<bits/stdc++.h>
using namespace std;
 
const int N = 2e6 + 7;
const int inf = 1e9 + 7;
const long long infll = 1e18 + 7;
 
int n, q;
long long a[N], b[N];
long long seg[4 * N][2][2];
 
void update(int id, int l, int r, int pos, int v) {
    if (r < pos ||  l > pos) return;
    if (l == r) {
        if (l == pos) b[l] += v;
        seg[id][1][1] = abs(b[l]);
        seg[id][0][0] = 0;
        return;
    }
    int mid = (l + r) / 2;
    update(id * 2, l, mid, pos, v);
    update(id * 2 + 1, mid + 1, r, pos, v);
    int x = id * 2, y = id * 2 + 1;
    //merge two segment;
    seg[id][0][0] = max(seg[x][0][0] + seg[y][0][0], max(seg[x][0][1] + seg[y][0][0], seg[x][0][0] + seg[y][1][0]));
    seg[id][1][0] = max(seg[x][1][0] + seg[y][0][0], max(seg[x][1][1] + seg[y][0][0], seg[x][1][0] + seg[y][1][0]));
    seg[id][0][1] = max(seg[x][0][0] + seg[y][0][1], max(seg[x][0][1] + seg[y][0][1], seg[x][0][0] + seg[y][1][1]));
    seg[id][1][1] = max(seg[x][1][0] + seg[y][0][1], max(seg[x][1][1] + seg[y][0][1], seg[x][1][0] + seg[y][1][1]));
    if ((b[mid] < 0 && b[mid + 1] < 0) || (b[mid] > 0 && b[mid + 1] > 0)) {
        seg[id][0][0] = max(seg[id][0][0], seg[x][0][1] + seg[y][1][0]);
        seg[id][1][0] = max(seg[id][0][0], seg[x][1][1] + seg[y][1][0]);
        seg[id][0][1] = max(seg[id][0][0], seg[x][0][1] + seg[y][1][1]);
        seg[id][1][1] = max(seg[id][0][0], seg[x][1][1] + seg[y][1][1]);
    }
}
int main() 
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i < n; i++) {
        update(1, 1, n - 1, i, a[i] - a[i + 1]);
    }
    while (q--) {
        int l, r;
        long long v; 
        cin >> l >> r >> v;
        update(1, 1, n - 1, l - 1, -v);
        update(1, 1, n - 1, r, v);
        cout << seg[1][1][1];
        if (q > 0) cout << '\n';
    }
    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 40 / 40
• Subtask 3: 55 / 55