Submission #1152378

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152378		hmm789	Sjeckanje (COCI21_sjeckanje)	C++20	110 / 110	378 ms	37808 KiB

Main

#include "bits/stdc++.h"
using namespace std;
#define int long long
#define double long double
#define INF 1000000000000000000
#define MOD 1000000007

int a[200001];
int sgn(int x) {
    return x >= 0;
}

struct node {
    int s, e, m, v[2][2]; // 0 = no take first/last, 1 = take
    node *l, *r;
    node(int _s, int _e) {
        s = _s, e = _e, m = (s+e)/2, v[0][0] = v[0][1] = v[1][0] = v[1][1] = 0;
        if(s != e) {
            l = new node(s, m);
            r = new node(m+1, e);
        }
    }
    void update(int x, int val) {
        if(s == e) {
            v[1][1] = abs(val);
            return;
        } else if(x > m) r->update(x, val);
        else l->update(x, val);
        if(sgn(a[m]) == sgn(a[m+1])) {
            for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++) {
                v[i][j] = 0;
                for(int k = 0; k < 2; k++) for(int k1 = 0; k1 < 2; k1++) {
                    v[i][j] = max(v[i][j], l->v[i][k] + r->v[k1][j]);
                }
            }
        } else {
            for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++) {
                v[i][j] = 0;
                for(int k = 0; k < 2; k++) for(int k1 = 0; k1 < 2; k1++) {
                    if(k == 1 && k1 == 1) continue;
                    v[i][j] = max(v[i][j], l->v[i][k] + r->v[k1][j]);
                }
            }
        }
    }
    int get() {
        int ans = 0;
        for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++) ans = max(ans, v[i][j]);
        return ans;
    }
} *root;

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, q, l, r, x;
    cin >> n >> q;
    int b[n];
    for(int i = 0; i < n; i++) {
        cin >> b[i];
    }
    root = new node(0, n);
    for(int i = 1; i < n; i++) {
        a[i] = b[i]-b[i-1];
        root->update(i, a[i]);
    }
    while(q--) {
        cin >> l >> r >> x;
        if(l-1 >= 1) {
            a[l-1] += x;
            root->update(l-1, a[l-1]);
        }
        if(r < n) {
            a[r] -= x;
            root->update(r, a[r]);
        }
        cout << root->get() << '\n';
    }
}

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