Submission #541808

#	Time	Username	Problem	Language	Result	Execution time	Memory
541808		AlperenT	Sjeckanje (COCI21_sjeckanje)	C++17	0 / 110	1 ms	340 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;

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

struct Item{
    long long mn, mx, len;
};

struct SegNode{
    Item pre, suf;
    long long ans, len;
};

bool isgood(long long mn, long long mx, long long mn2, long long mx2){
    return mn2 > mx || mx2 < mn;
}

struct SegTree{
    SegNode tree[N * 4];
    long long laadd[N * 4];

    SegNode merge(SegNode a, SegNode b){
        SegNode c;

        c.ans = a.ans + b.ans, c.len = a.len + b.len;

        c.pre = a.pre, c.suf = b.suf;

        if(a.pre.len == a.len && isgood(a.pre.mn, a.pre.mx, b.pre.mn, b.pre.mx)){
            c.pre = {min(a.pre.mn, b.pre.mn), max(a.pre.mx, b.pre.mx), a.pre.len + b.pre.len};
        }
        if(b.suf.len == b.len && isgood(a.suf.mn, a.suf.mx, b.suf.mn, b.suf.mx)){
            c.suf = {min(a.suf.mn, b.suf.mn), max(a.suf.mx, b.suf.mx), a.suf.len + b.suf.len};
        }

        if(c.pre.len < a.len && c.suf.len < b.len){
            if(isgood(a.suf.mn, a.suf.mx, b.pre.mn, b.pre.mx)){
                c.ans += max(a.suf.mx, b.pre.mx) - min(a.suf.mn, b.pre.mn);
            }
            else{
                c.ans += a.suf.mx - a.suf.mn + b.pre.mx - b.pre.mn;
            }
        }

        return c;
    }

    void push(int v){
        if(laadd[v]){
            tree[v].pre.mn += laadd[v], tree[v].pre.mx += laadd[v], tree[v].suf.mn += laadd[v], tree[v].suf.mx += laadd[v];

            if(v * 2 < N * 4){
                laadd[v * 2] += laadd[v], laadd[v * 2 + 1] += laadd[v];
            }

            laadd[v] = 0;
        }
    }

    void build(int v = 1, int l = 1, int r = n){
        if(l == r) tree[v] = {{arr[l], arr[l], 1}, {arr[l], arr[l], 1}, 0, 1};
        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 rangeadd(int l, int r, long long val, int v = 1, int tl = 1, int tr = n){
        if(l > r) return;
        else{
            push(v);

            if(l == tl && r == tr) laadd[v] += val, push(v);
            else{
                int tm = tl + (tr - tl) / 2;

                rangeadd(l, min(tm, r), val, v * 2, tl, tm);
                rangeadd(max(tm + 1, l), r, val, v * 2 + 1, tm + 1, tr);

                push(v * 2), push(v * 2 + 1);

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

    long long getans(){
        push(1);

        long long ans = tree[1].ans;

        ans += tree[1].pre.mx - tree[1].pre.mn;

        if(tree[1].pre.len != tree[1].len) ans += tree[1].suf.mx - tree[1].suf.mn;

        return ans;
    }
};

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];

    sgt.build();

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

        sgt.rangeadd(l, r, x);

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

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