Submission #479164

#	Time	Username	Problem	Language	Result	Execution time	Memory
479164		Karliver	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	340 ms	27988 KiB

Main

    
#include <bits/stdc++.h>

#define FIXED_FLOAT(x)  std::fixed <<std::setprecision(20) << (x)
#define all(v) (v).begin(), (v).end()
using namespace  std;
#define forn(i,n) for (int i = 0; i < (n); ++i)
#define rforn(i, n) for(int i = (n) - 1;i >= 0;--i)
#define sz(x) (int)x.size()

using ll = long long;
int mod = (ll)1e9 + 7;
#define PI acos(-1)
typedef pair<int, int> pairs;

const int INF = 1e9 + 1;
const int N = 2e5 + 2;
const double eps = 1e-7;

template <class T> using V = vector<T>;  
template <class T> using VV = V<V<T>>;  
template<class T, size_t SZ> using AR = array<T, SZ>;
template<class T> using PR = pair<T, T>;
template <typename XPAX>
bool ckma(XPAX &x, XPAX y) {
    return (x < y ? x = y, 1 : 0);
}
template <typename XPAX>
bool ckmi(XPAX &x, XPAX y) {
    return (x > y ? x = y, 1 : 0);
}
int n, q;

ll S[4 * N][2][2];
int a[N], b[N];
void merge(int t, int x, int y) {
    
    forn(i, 2) forn(j, 2) S[t][i][j] = max(S[x][i][0] + S[y][0][j], S[x][i][1] + S[y][1][j]);
}
void upd(int pos, int val, int p = 1, int l = 1, int r = n) {
    if(l == r) {
        forn(i, 2) forn(j, 2) S[p][i][j] = 0;
        if(val < 0)S[p][0][0] = -val;
        else S[p][1][1] = val;
        return;
    }
    int rm = (l + r) >> 1;

    if(pos <= rm)
        upd(pos, val, p << 1, l, rm);
    else upd(pos, val, p << 1 | 1, rm + 1, r);
    
    merge(p, p << 1, p << 1 | 1);
}

VV<ll> range_qur(int il, int ir, int p = 1, int l = 1, int  r = n) {
    if(r < il || l > ir) {
        VV<ll> f(2, V<ll>(2));
        return f;
    }
    if(il <= l && r <= ir) {
        VV<ll> f(2, V<ll>(2));
        forn(i, 2) forn(j, 2) f[i][j] = S[p][i][j];
        return f;
    }

    int rm = (l + r) >> 1;

    auto L = range_qur(il, ir, p << 1, l, rm);
    auto R = range_qur(il, ir, p << 1 | 1, rm + 1, r);

    VV<ll>f(2, V<ll>(2));
    forn(i, 2) forn(j, 2) f[i][j] = max(L[i][0] + R[0][j], L[i][1] + R[1][j]);
    return f;
}


void solve() {

    cin >> n >> q;
    

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

    --n;
    for(int i = n;i;--i) {
        a[i] = b[i + 1] - b[i];
        upd(i, a[i]);
    }


    while(q--) {
        int l, r, x;
        cin >> l >> r >> x;
        /*
        if(t == 1) {
            
            a[l] = r;
            if(l >  1) {
                upd(l - 1, a[l] - a[l - 1]);
            }
            if(l > 0 && l <= n) {
                upd(l, a[l + 1] - a[l]);
            }
        }
        else {
            if(l == r) {
                cout << 0 << '\n';
                continue;
            }
            auto D = range_qur(l, r - 1);
            ll ret = 0;
            forn(i, 2) forn(j, 2) ckma(ret, D[i][j]);
            cout << ret << '\n';
        }
        */

        if(l > 1)
            upd(l - 1, (a[l - 1] += x));

        if(r <= n)
            upd(r, (a[r] -= x));

        cout << max({S[1][0][0], S[1][0][1], S[1][1][0], S[1][1][1]}) << '\n';


    }



}
void test_case() {
    int t;
    cin >> t;
    forn(p, t) {

        //cout << "Case #" << p + 1 << ": ";
        solve();
    }
}
int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();

}

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