Submission #907496

#	Time	Username	Problem	Language	Result	Execution time	Memory
907496		a_l_i_r_e_z_a	Sjeckanje (COCI21_sjeckanje)	C++17	0 / 110	2 ms	2392 KiB

Main

// In the name of God

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pii;
typedef pair<ll, ll> pll;

#define pb push_back
#define S second
#define F first
#define mp make_pair
#define smax(x, y) (x) = max((x), (y))
#define smin(x, y) (x) = min((x), (y))
#define all(x) (x).begin(), (x).end()
#define len(x) ((ll)(x).size())

const ll maxn = 2e5 + 5;
const ll inf = 1e16 + 7;
ll n, q, a[maxn];
ll lazy[maxn << 2];
struct D{
    ll ans, left, right, al, ar, is;
} node[maxn << 2];

D combine(D x, D y){
    D res = {x.ans + y.ans, x.left, y.right, x.al, y.ar, 1};
    if(x.right == y.left) return res;
    if(x.right > y.left){
        ll delta = x.right - y.left;
        if(x.ar != -inf && x.ar < x.right) delta -= abs(x.ar - x.right);
        if(y.al != -inf && y.al > y.left) delta -= abs(y.al - y.left);
        if(delta <= 0) return res;
        res.ans += delta;
        if(!x.is){
            if(x.al == -inf) res.al = y.left;
            else if(x.al == x.right){
                if(x.left < x.right) res.al = -inf;
            }
        } 
        if(!y.is){
            if(y.ar == -inf) res.ar = x.right;
            else if(y.ar == y.left){
                if(y.right > y.left) res.ar = -inf;
            }
        }
        if(x.is == 0 && y.is == 0){
            if(x.ar == -inf || x.ar > x.right){
                if(y.al == -inf || y.al < x.left) res.is = 0;
            }
        }
    }
    if(x.right < y.left){
        ll delta = abs(x.right - y.left);
        if(x.ar != -inf && x.ar > x.right) delta -= abs(x.ar - x.right);
        if(y.al != -inf && y.al < y.left) delta -= abs(y.al - y.left);
        if(delta <= 0) return res;
        res.ans += delta;
        if(!x.is){
            if(x.al == -inf) res.al = y.left;
            else if(x.al == x.right){
                if(x.left > x.right) res.al = -inf;
            }
        } 
        if(!y.is){
            if(y.ar == -inf) res.ar = x.right;
            else if(y.ar == y.left){
                if(y.right < y.left) res.ar = -inf;
            }
        }
        if(x.is == 0 && y.is == 0){
            if(x.ar == -inf || x.ar < x.right){
                if(y.al == -inf || y.al > x.left) res.is = 0;
            }
        }
    }
    return res;
}

void build(ll l = 0, ll r = n, ll id = 1){
    if(l == r - 1){
        node[id].ans = 0;
        node[id].left = a[l];
        node[id].right = a[l];
        node[id].al = -inf;
        node[id].ar = -inf;
        node[id].is = 0;
        return;
    }
    ll mid = (l + r) / 2;
    build(l, mid, id * 2);
    build(mid, r, id * 2 + 1);
    node[id] = combine(node[id * 2], node[id * 2 + 1]);
}

void change(ll x, ll id){
    node[id].right += x;
    node[id].left += x;
    if(node[id].al != -inf) node[id].al += x;
    if(node[id].ar != -inf) node[id].ar += x;
    lazy[id] += x;
}

void relax(ll id){
    change(lazy[id], id * 2);
    change(lazy[id], id * 2 + 1);
    lazy[id] = 0;
}

void upd(ll s, ll e, ll x, ll l = 0, ll r = n, ll id = 1){
    if(s <= l && r <= e){
        change(x, id);
        return;
    }
    if(e <= l || r <= s) return;
    ll mid = (l + r) / 2;
    relax(id);
    upd(s, e, x, l, mid, id * 2);
    upd(s, e, x, mid, r, id * 2 + 1);
    node[id] = combine(node[id * 2], node[id * 2 + 1]);
}

int32_t main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> q;
    for(ll i = 0; i < n; i++) cin >> a[i];
    build();
    while(q--){
        ll l, r, x; cin >> l >> r >> x;
        l--;
        upd(l, r, x);
        cout << node[1].ans << '\n';
    }

    return 0;
}

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