Submission #1208453

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208453		vanea	Sjeckanje (COCI21_sjeckanje)	C++20	110 / 110	363 ms	31040 KiB

Main

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

const int mxN = 1e6+10;
const ll INF = 1e18;

vector<ll> v, d;
array<ll, 6> st[mxN];
ll add[mxN];

array<ll, 6> comb(array<ll, 6> a, array<ll, 6> b) {
    array<ll, 6> ans = {0, 0, 0, 0, 0, 0};
    ans[5] = b[5];
    ans[4] = a[4];
    if((a[5] > 0 && b[4] <= 0) || (a[5] <= 0 && b[4] > 0)) {
        ans[0] = max({a[0]+b[3], a[2]+b[0], a[2]+b[3]});
        ans[1] = max({a[1]+b[2], a[3]+b[1], a[1]+b[1]});
        ans[2] = max({a[2]+b[2], a[2]+b[1], a[0]+b[1]});
        ans[3] = max({a[1]+b[3], a[3]+b[3], a[1]+b[0]});
    }
    else {

        ans[0] = max({a[2]+b[3], a[0]+b[3], a[2]+b[0], a[0]+b[0]});
        ans[2] = max({a[2]+b[1], a[2]+b[2], a[0]+b[1], a[0]+b[2]});
        ans[1] = max({a[1]+b[1], a[3]+b[1], a[1]+b[2], a[3]+b[2]});
        ans[3] = max({a[1]+b[3], a[1]+b[0], a[3]+b[3], a[3]+b[0]});
    }
    return ans;
}

void build(int node, int l, int r) {
    if(l == r) {
        st[node] = {abs(d[l]), 0, 0, 0, d[l], d[l]};
        return ;
    }
    int mid = (l+r)/2;
    build(node*2, l, mid);
    build(node*2+1, mid+1, r);
    st[node] = comb(st[node*2], st[node*2+1]);
}

void upd(int node, int l, int r, int k, ll x) {
    if(l == r && l == k) {
        st[node][5] += x; st[node][4] += x;
        st[node][0] = abs(st[node][4]);
        return ;
    }
    if(l > k || r < k) return ;
    int mid = (l+r)/2;
    upd(node*2, l, mid, k, x);
    upd(node*2+1, mid+1, r, k, x);
    st[node] = comb(st[node*2], st[node*2+1]);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    v.resize(n); d.resize(n);
    for(int i = 0; i < n; i++) {
        cin >> v[i];
    }
    for(int i = 0; i < n-1; i++) {
        d[i] = v[i]-v[i+1];
    }
    build(1, 0, n-2);
    while(q--) {
        int l, r; ll x;
        cin >> l >> r >> x; --l; --r;
        if(l) upd(1, 0, n-2, l-1, -x);
        upd(1, 0, n-2, r, x);
        cout << st[1][0] << '\n';
    }
    return 0;
}

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