Submission #673779

#	Time	Username	Problem	Language	Result	Execution time	Memory
673779		Trent	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	1071 ms	46948 KiB

Main

#include "bits/stdc++.h"
#include <cstring>
#include <fstream>

using namespace std;

#define ll long long
#define forR(i, x) for(int i = 0; i < x; ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define open(s) freopen(((string) s + ".in").c_str(), "r", stdin); freopen(((string) s + ".out").c_str(), "w", stdout)
#define all(i) i.begin(), i.end()
#define boost() cin.sync_with_stdio(0); cin.tie()
#define int ll

int sign(int g){
    return g == 0 ? 0 : g > 0 ? 1 : -1;
}

const int MN = 2e5 + 10, ME=4*MN;
// maximum total value if we remove [left][right]; lazy increase; left & right value; left & right sign (nex - cur)
struct node{int tot[2][2], lInc, lef, rig, lSig, rSig;};
node seg[ME];

void push(int v){
    if(2 * v + 1 < ME){
        seg[2*v].lef += seg[v].lInc;
        seg[2*v].rig += seg[v].lInc;
        seg[2*v+1].lef += seg[v].lInc;
        seg[2*v+1].rig += seg[v].lInc;
        seg[2*v].lInc += seg[v].lInc;
        seg[2*v+1].lInc += seg[v].lInc;
        seg[v].lInc = 0;
    }
}

void upd(int v, int nl, int nr, int ul, int ur, int by){
    if(nl > ur || nr < ul) return;
    else if(nl == ul && nr == ur){
        seg[v].lInc += by;
        seg[v].lef += by;
        seg[v].rig += by;
    } else {
        push(v);
        int mid = (nl + nr) / 2;
        upd(2*v, nl, mid, ul, min(mid, ur), by);
        upd(2*v+1, mid+1, nr, max(mid+1, ul), ur, by);

        seg[v].lef = seg[2*v].lef;
        seg[v].rig = seg[2*v+1].rig;
        assert(seg[v].lInc == 0);
        forR(lr, 2) forR(rr, 2){
            int& edit = seg[v].tot[lr][rr];
            edit = seg[2*v].tot[lr][0] + seg[2*v+1].tot[0][rr];

            if(nr - mid - rr > 0 && mid - nl + 1 - lr > 0){
                int delta = seg[2*v+1].lef - seg[2*v].rig;
                int dSign = sign(delta);
                int lefAdd = seg[2*v].rSig == dSign ? seg[2*v].tot[lr][0] : seg[2*v].tot[lr][1];
                int rigAdd = seg[2*v+1].lSig == dSign ? seg[2*v+1].tot[0][rr] : seg[2*v+1].tot[1][rr];
                edit = max(edit, lefAdd + abs(delta) + rigAdd);
            }
        }
        seg[v].lSig = mid > nl ? seg[2*v].lSig : sign(seg[2*v+1].lef - seg[2*v].rig);
        seg[v].rSig = mid + 1 < nr ? seg[2*v+1].rSig : sign(seg[2*v+1].lef - seg[2*v].rig);
    }
}


signed main() {
    int n, q; cin >> n >> q;
    REP(i, 1, n + 1) {
        int v; cin >> v;
        upd(1, 1, n, i, i, v);
    }
    forR(g, q){
        int l, r, x; cin >> l >> r >> x;
        upd(1, 1, n, l, r, x);
        cout << seg[1].tot[0][0] << '\n';
    }
}

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