Submission #440320

#	Time	Username	Problem	Language	Result	Execution time	Memory
440320		SirCovidThe19th	Sjeckanje (COCI21_sjeckanje)	C++14	110 / 110	1411 ms	26220 KiB

Main

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

#define ll long long
#define FOR(i, x, y) for (int i = x; i < y; i++)

const ll mx1 = 2e5+5, mx2 = (1<<18), inf = LLONG_MAX/2;

ll n, q, sz, diff[mx1], mid[mx2], seg[mx2*2][2][2];

void upd(ll i, ll val){
    i += sz; seg[i][1][0] = seg[i][0][1] = -inf; seg[i][1][1] = abs(val);
    auto sgn = [](ll val){ return (val < 0) ? -1 : 1; };
    for (i /= 2; i > 0; i /= 2){
        FOR(l, 0, 2) FOR(r, 0, 2){ ll& curr = seg[i][l][r]; curr = -inf;
            curr = max(curr, seg[i*2][l][0]+seg[i*2+1][0][r]);
            curr = max(curr, seg[i*2][l][1]+seg[i*2+1][0][r]);
            curr = max(curr, seg[i*2][l][0]+seg[i*2+1][1][r]);
            if (sgn(diff[mid[i]])*sgn(diff[mid[i]+1]) != -1)
                curr = max(curr, seg[i*2][l][1]+seg[i*2+1][1][r]);
        }
    }
}

int main(){ 
    cin >> n >> q; sz = pow(2, ceil(log2(n-1)));
    FOR(i, 1, sz){
        int l = i, r = i; 
        while (r < sz) l = l*2, r = r*2+1;
        mid[i] = (l+r)/2-sz; mid[i] = min(mid[i], mx1-1);
    }ll prev; FOR(i, 0, n){ 
        ll a; cin >> a;
        if (i > 0) diff[i-1] = a-prev, upd(i-1, diff[i-1]); 
        prev = a;
    }while (q--){
        ll l, r, x; cin >> l >> r >> x; l--; r--;
        if (l-1 >= 0) diff[l-1] += x, upd(l-1, diff[l-1]);
        if (r < n-1) diff[r] -= x, upd(r, diff[r]);
        cout<<max({seg[1][0][0], seg[1][1][0], seg[1][0][1], seg[1][1][1]})<<endl;
    }
}

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