Submission #891473

#	Time	Username	Problem	Language	Result	Execution time	Memory
891473		phongcd	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	324 ms	41300 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ii pair <int, int>
#define ill pair <ll, ll>
#define ild pair <ld, ld>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define file "test"
using namespace std;
const int N = 2e5 + 2;
const int M = 31;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
const ll base = 311;
const int BLOCK_SIZE = 400;

int n, q, a[N];
ll lazy[4 * N];

struct node {
    ll l, r, uu, dd, ud, du;
} st[4 * N];

node cb(node a, node b) {
    node c;
    c.l = a.l, c.r = b.r;
    ll tu = max(0ll, b.l - a.r);
    ll td = max(0ll, a.r - b.l);
    c.uu = max({a.uu + b.uu + tu, a.uu + b.du, a.ud + b.uu, a.ud + b.du + td});
    c.dd = max({a.du + b.ud + tu, a.du + b.dd, a.dd + b.ud, a.dd + b.dd + td});
    c.ud = max({a.uu + b.ud + tu, a.uu + b.dd, a.ud + b.ud, a.ud + b.dd + td});
    c.du = max({a.du + b.uu + tu, a.du + b.du, a.dd + b.uu, a.dd + b.du + td});
    return c;
}

void build(int id, int l, int r) {
    if (l == r) {
        st[id].l = st[id].r = a[l];
        st[id].ud = st[id].du = -INF;
        return ;
    }
    int mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    st[id] = cb(st[id << 1], st[id << 1 | 1]);
}

void down(int id) {
    ll t = lazy[id];
    if (!t) return ;
    st[id << 1].l += t, st[id << 1].r += t;
    st[id << 1 | 1].l += t, st[id << 1 | 1].r += t;
    lazy[id << 1] += t, lazy[id << 1 | 1] += t;
    lazy[id] = 0;
}

void upd(int id, int l, int r, int u, int v, ll w) {
    if (v < l || r < u) return ;
    if (u <= l && r <= v) {
        st[id].l += w, st[id].r += w;
        lazy[id] += w;
        return ;
    }
    down(id);
    int mid = (l + r) >> 1;
    upd(id << 1, l, mid, u, v, w);
    upd(id << 1 | 1, mid + 1, r, u, v, w);
    st[id] = cb(st[id << 1], st[id << 1 | 1]);
}

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

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

    build(1, 1, n);

    ll l, r, x;
    while (q --) {
        cin >> l >> r >> x;
        upd(1, 1, n, l, r, x);

        node res = st[1];
        ll ans =  max({res.uu, res.dd, res.ud, res.du});
        cout << ans << '\n';
    }
}
/*
     /\_/\ zzZ
    (= -_-)
    / >u  >u
*/

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