Submission #1172838

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

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;
int seg[800005][2][2], a[200005];
void upd(int i, int l, int r, int x)
{
    if (l==r)
    {
        seg[i][0][0]=abs(a[x]);
        return;
    }
    int mid=(l+r)/2;
    if (x<=mid)
        upd(i*2, l, mid, x);
    else
        upd(i*2+1, mid+1, r, x);
    for (int j=0; j<2; j++)
    {
        for (int k=0; k<2; k++)
        {
            seg[i][j][k]=0;
            for (int l=0; l<2; l++)
                for (int m=0; m<2; m++)
                    if (l || m || a[mid]*a[mid+1]>0)
                        seg[i][j][k]=max(seg[i][j][k], seg[i*2][j][l]+seg[i*2+1][m][k]);
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, q;
    cin >> n >> q;
    for (int i=1; i<=n; i++)
        cin >> a[i];
    for (int i=1; i<n; i++)
    {
        a[i]=a[i+1]-a[i];
        upd(1, 1, n-1, i);
    }
    for (int i=1; i<=q; i++)
    {
        int l, r, x;
        cin >> l >> r >> x;
        a[l-1]+=x;
        a[r]-=x;
        if (l>1)
            upd(1, 1, n-1, l-1);
        upd(1, 1, n-1, r);
        cout << max(max(seg[1][0][0], seg[1][0][1]), max(seg[1][1][0], seg[1][1][1])) << '\n';
    }
}

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