Submission #874820

#	Time	Username	Problem	Language	Result	Execution time	Memory
874820		vjudge1	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	404 ms	28704 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;
int seg[800100][2][2], arr[200100];
void merge(int n, int mid) {
	for (int i=0;i<2;i++)
	    for (int j=0;j<2;j++) {
		    seg[n][i][j]=-1e18;
		    for (int k=0;k<2;k++)
		        for (int l=0;l<2;l++)
		            if (l!=1||k!=1||arr[mid]*arr[mid+1]>=0)
		                seg[n][i][j]=max(seg[n][i][j],seg[n*2][i][k]+seg[n*2+1][l][j]);
	    }
}
void upd(int p,int l,int r,int pos) {
	if (l==r) {
		seg[p][1][1]=abs(arr[l]);
		return;
	}
	int mid=l+r>>1;
	if (pos<=mid)
	    upd(p*2,l,mid,pos);
	else
	    upd(p*2+1,mid+1,r,pos);
	merge(p,mid);
}
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    for(int i = 1; i <= n; i++)
        cin >> arr[i];
    for(int i = n; --i;)
        arr[i+1]-=arr[i], upd(1,1,n,i+1);
    arr[1]=0;
    for(int i = 0; i < q; i++) {
        int l, r, x;
        cin >> l >> r >> x;
        if(l!=1)
            arr[l]+=x,
            upd(1,1,n,l);
        if(r!=n)
            arr[r+1]-=x,
            upd(1,1,n,r+1);
        cout << max(max(seg[1][0][0],seg[1][0][1]),max(seg[1][1][0],seg[1][1][1])) << '\n';
    }
}

Compilation message (stderr)

Main.cpp: In function 'void upd(long long int, long long int, long long int, long long int)':
Main.cpp:20:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |  int mid=l+r>>1;
      |          ~^~

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