Submission #1208346

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208346		vanea	Sjeckanje (COCI21_sjeckanje)	C++20	0 / 110	0 ms	320 KiB

Main

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

const int mxN = 1e6+10;

array<ll, 5> st[mxN];
vector<int> v;
ll add[mxN];

array<ll, 5> comb(array<ll, 5> a, array<ll, 5> b, int l, int r) {
    array<ll, 5> ans = {0, 0, 0, 0, 0};
    if(r-l+1 <= 3) {
        if(r-l+1 == 2) {
            ans[0] = abs(a[1]-b[1]);
            ans[1] = min(a[1], b[1]);
            ans[2] = max(a[1], b[1]);
            ans[3] = ans[1];
            ans[4] = ans[2];
        }
        else {
            if(a[1] == a[2]) swap(a, b);
            if(b[1] < a[1]) {
                ans[0] = a[2]-b[1];
                ans[1] = b[1];
                ans[2] = a[2];
                ans[3] = b[1];
                ans[4] = a[2];
            }
            else if(b[1] > a[2]) {
                ans[0] = b[1]-a[1];
                ans[1] = a[1];
                ans[2] = b[1];
                ans[3] = a[1];
                ans[4] = b[1];
            }
        }
        return ans;
    }
    if(a[2] < b[3]) {
        ans[0] = a[0] + b[0] + (b[3] - a[2]);
        ans[1] = b[1]; ans[2] = b[2];
        ans[3] = a[3]; ans[4] = a[4];
        ll curr = b[4]-a[1];
        if(a[0] == a[2]-a[1]) {
            ans[4] = b[4];
        }
        if(b[0] == b[2]-b[1]) {
            ans[1] = a[1];
        }
    }
    else if(b[4] < a[1]) {
        ans[0] = a[0] + b[0] + (a[1]-b[4]);
        ans[1] = b[1]; ans[2] = b[2];
        ans[3] = a[3]; ans[4] = a[4];
        if(a[0] == a[2]-a[1]) {
            ans[3] = b[3];
        }
        if(b[0] == b[2]-b[1]) {
            ans[2] = a[2];
        }
    }
    else {
        ans[0] = a[0] + b[0];
        ans[1] = b[1]; ans[2] = b[2];
        ans[3] = a[3]; ans[4] = a[4];
    }
    return ans;
}

void build(int node, int l, int r) {
    if(l == r) {
        st[node] = {0, v[l], v[l], v[l], v[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], l, r);
}

void push(int node, int l, int r) {
    if(add[node]) {
        add[node*2] += add[node];
        add[node*2+1] += add[node];
        for(int j = 1; j <= 4; j++) {
            st[node*2][j] += add[node];
            st[node*2+1][j] += add[node];
        }
    }
    add[node] = 0;
}

void upd(int node, int l, int r, int l1, int r1, ll k) {
    push(node, l, r);
    if(l1 <= l && r <= r1) {
        for(int j = 1; j <= 4; j++) {
            st[node][j] += k;
        }
        add[node] += k;
        return ;
    }
    if(l > r1 || r < l1) return ;
    int mid = (l+r)/2;
    upd(node*2, l, mid, l1, r1, k);
    upd(node*2+1, mid+1, r, l1, r1, k);
    st[node] = comb(st[node*2], st[node*2+1], l, r);
}

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

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