Submission #541873

#	Time	Username	Problem	Language	Result	Execution time	Memory
541873		AlperenT	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	544 ms	32024 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;

long long n, q, arr[N], l, r, x;

struct SegNode{
    int l, r;
    long long OO, OX, XO, XX;
};

struct SegTree{
    SegNode tree[N * 4];

    SegNode merge(SegNode a, SegNode b){
        SegNode c = {a.l, b.r, 0, 0, 0, 0};

        // OO

        if(max(arr[a.r], arr[b.l]) > 0 && min(arr[a.r], arr[b.l]) < 0){
            c.OO = a.OO + b.OO - min(abs(arr[a.r]), abs(arr[b.l]));
        }
        else c.OO = a.OO + b.OO;

        c.OO = max({c.OO, a.OO + b.XO, a.OX + b.OO, a.OX + b.XO});

        // OX

        if(max(arr[a.r], arr[b.l]) > 0 && min(arr[a.r], arr[b.l]) < 0){
            c.OX = a.OO + b.OX - min(abs(arr[a.r]), abs(arr[b.l]));
        }
        else c.OX = a.OO + b.OX;

        c.OX = max({c.OX, a.OO + b.XX, a.OX + b.OX, a.OX + b.XX});

        // XO

        if(max(arr[a.r], arr[b.l]) > 0 && min(arr[a.r], arr[b.l]) < 0){
            c.XO = a.XO + b.OO - min(abs(arr[a.r]), abs(arr[b.l]));
        }
        else c.XO = a.XO + b.OO;

        c.XO = max({c.XO, a.XO + b.XO, a.XX + b.OO, a.XX + b.XO});

        // XX

        if(max(arr[a.r], arr[b.l]) > 0 && min(arr[a.r], arr[b.l]) < 0){
            c.XX = a.XO + b.OX - min(abs(arr[a.r]), abs(arr[b.l]));
        }
        else c.XX = a.XO + b.OX;

        c.XX = max({c.XX, a.XO + b.XX, a.XX + b.OX, a.XX + b.XX});

        return c;
    }

    void build(int v = 1, int l = 1, int r = n - 1){
        if(l > r) return;
        else if(l == r) tree[v] = {l, l, abs(arr[l]), 0, 0, 0};
        else{
            int m = l + (r - l) / 2;

            build(v * 2, l, m); build(v * 2 + 1, m + 1, r);

            tree[v] = merge(tree[v * 2], tree[v * 2 + 1]);
        }
    }

    void update(int pos, long long val, int v = 1, int l = 1, int r = n - 1){
        if(l > r) return;
        else if(l == r){
            arr[l] += val;
            tree[v].OO = abs(arr[l]);
        }
        else{
            int m = l + (r - l) / 2;

            if(pos <= m) update(pos, val, v * 2, l, m);
            else update(pos, val, v * 2 + 1, m + 1, r);

            tree[v] = merge(tree[v * 2], tree[v * 2 + 1]);
        }
    }

    long long getans(){
        return max({tree[1].OO, tree[1].OX, tree[1].XO, tree[1].XX});
    }
};

SegTree sgt;

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

    cin >> n >> q;

    for(int i = 1; i <= n; i++) cin >> arr[i];

    for(int i = 1; i <= n - 1; i++) arr[i] = arr[i + 1] - arr[i];

    sgt.build();

    while(q--){
        cin >> l >> r >> x;

        if(l - 1 >= 1) sgt.update(l - 1, x);
        if(r <= n - 1) sgt.update(r, -x);

        cout << sgt.getans() << "\n";
    }
}

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