Submission #1012679

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012679		gyg	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	927 ms	52716 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const int MAX_N = 2e5 + 5;
const lint INF = 1e16;

int n, q;
array<lint, MAX_N> a;

struct Node {
    lint val;
    lint maxmax, maxmin, minmax, minmin;
    lint l_max, l_min, r_max, r_min;
} st[4 * MAX_N];
lint lazy[4 * MAX_N];


Node merge(Node& x, Node& y) {
    Node ans;
    ans.val = max({x.val + y.val, x.r_min + y.l_max, x.r_max + y.l_min});
    ans.maxmax = max({x.l_max + y.r_max, x.maxmax + y.minmax, x.maxmin + y.maxmax, x.maxmax, y.maxmax});
    ans.maxmin = max({x.l_max + y.r_min, x.maxmax + y.minmin, x.maxmin + y.maxmin, x.maxmin, y.maxmin});
    ans.minmax = max({x.l_min + y.r_max, x.minmax + y.minmax, x.minmin + y.maxmax, x.minmax, y.minmax});
    ans.minmin = max({x.l_min + y.r_min, x.minmax + y.minmin, x.minmin + y.maxmin, x.minmin, y.minmin});
    ans.l_max = max({x.l_max + y.val, x.maxmax + y.l_min, x.maxmin + y.l_max, y.l_max});
    ans.l_min = max({x.l_min + y.val, x.minmax + y.l_min, x.minmin + y.l_max, y.l_min});
    ans.r_max = max({x.val + y.r_max, x.r_max + y.minmax, x.r_min + y.maxmax, x.r_max});
    ans.r_min = max({x.val + y.r_min, x.r_max + y.minmin, x.r_min + y.maxmin, x.r_min});
    return ans;
}
void build(int u = 1, int lo = 1, int hi = n) {
    if (lo == hi) {
        st[u].val = 0;
        st[u].l_max = st[u].r_max = a[lo];
        st[u].l_min = st[u].r_min = -a[lo];
        st[u].maxmax = st[u].maxmin = st[u].minmax = st[u].minmin = -INF;
        return;
    }
    int mid = (lo + hi) / 2;
    build(2 * u, lo, mid), build(2 * u + 1, mid + 1, hi);
    st[u] = merge(st[2 * u], st[2 * u + 1]);
}

void propogate(int u) {
    if (lazy[u] == 0) return;
    for (int v : {2 * u, 2 * u + 1}) {
        st[v].l_max += lazy[u], st[v].r_max += lazy[u];
        st[v].l_min -= lazy[u], st[v].r_min -= lazy[u];
        st[v].maxmax += 2 * lazy[u], st[v].minmin -= 2 * lazy[u];
        lazy[v] += lazy[u];
    }
    lazy[u] = 0;
}
void update(int l, int r, lint x, int u = 1, int lo = 1, int hi = n) {
    if (r < lo || hi < l) return;
    if (l <= lo && hi <= r) {
        st[u].l_max += x, st[u].r_max += x;
        st[u].l_min -= x, st[u].r_min -= x;
        st[u].maxmax += 2 * x, st[u].minmin -= 2 * x;
        lazy[u] += x;
        return;
    }
    propogate(u);
    int mid = (lo + hi) / 2;
    update(l, r, x, 2 * u, lo, mid), update(l, r, x, 2 * u + 1, mid + 1, hi);
    st[u] = merge(st[2 * u], st[2 * u + 1]);
}

void debug(int u = 1, int lo = 1, int hi = n) {
    cout << lo << " " << hi << ": " << endl;
    cout << "VAL " << st[u].val << endl;
    cout << "MAXMAX " << st[u].maxmax << endl;
    cout << "MAXMIN " << st[u].maxmin << endl;
    cout << "MINMAX " << st[u].minmax << endl;
    cout << "MINMIN " << st[u].minmin << endl;
    cout << "LMAX " << st[u].l_max << endl;
    cout << "LMIN " << st[u].l_min << endl;
    cout << "RMAX " << st[u].r_max << endl;
    cout << "RMIN " << st[u].r_min << endl;
    cout << "LAZY " << lazy[u] << endl;

    if (lo == hi) return;
    propogate(u);
    int mid = (lo + hi) / 2;
    debug(2 * u, lo, mid), debug(2 * u + 1, mid + 1, hi);
}

int main() {
    // freopen("sje.in", "r", stdin);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];

    build();
    
    for (int i = 1; i <= q; i++) {
        int l, r; cin >> l >> r;
        lint x; cin >> x;
        update(l, r, x);
        // if (i == q) debug();
        cout << st[1].val << '\n';
    }
}

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