Submission #373118

#	Time	Username	Problem	Language	Result	Execution time	Memory
373118		sam571128	Sjeckanje (COCI21_sjeckanje)	C++14	110 / 110	779 ms	38124 KiB

Main

#include <bits/stdc++.h>

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 2e5+5;
struct node{
	int dp[2][2], lval, rval;
};
node d[N*4];
int n,q;


node combine(node a, node b){
	node res;
	res.lval = a.lval, res.rval = b.rval;
	for(int i = 0;i < 2;i++){
		for(int j = 0;j < 2;j++){
			res.dp[i][j] = -1e14;
			res.dp[i][j] = max({res.dp[i][j], a.dp[i][0]+b.dp[1][j],a.dp[i][0]+b.dp[0][j],a.dp[i][1]+b.dp[0][j]});
			if(a.rval*b.lval >= 0) res.dp[i][j] = max(res.dp[i][j], a.dp[i][1]+b.dp[1][j]);
		}
	}
	return res;
}

void build(int arr[], int idx = 1, int l = 1, int r = n){
	if(l==r){
		d[idx].lval = d[idx].rval = arr[l];
		d[idx].dp[1][0] = d[idx].dp[0][1] = -1e14;
		d[idx].dp[0][0] = 0;
		d[idx].dp[1][1] = abs(arr[l]);
	}else{
		int mid = l+r>>1;
		build(arr,idx<<1,l,mid);
		build(arr,idx<<1|1,mid+1,r);
		d[idx] = combine(d[idx<<1],d[idx<<1|1]);
	}
}


void modify(int pos, int val, int idx = 1, int l = 1, int r = n){
	if(l==r){
		d[idx].lval += val;
		d[idx].rval += val;
		d[idx].dp[1][1] = abs(d[idx].lval);
		return;
	}else{
		int mid = l+r>>1;
		if(pos <= mid) modify(pos,val,idx<<1,l,mid);
		else modify(pos,val,idx<<1|1,mid+1,r);
		d[idx] = combine(d[idx<<1],d[idx<<1|1]);
	}
}

signed main(){
	fastio
	cin >> n >> q;
	int arr[n+1], dd[n+1] = {};
	for(int i = 1;i <= n;i++) cin >> arr[i];
	for(int i = 1;i < n;i++){
		dd[i] = arr[i+1]-arr[i];
	}
	build(dd);
	while(q--){
		int l,r,x;
		cin >> l >> r >> x;
		if(l>1) modify(l-1,x);
		if(r<n) modify(r,-x);
		cout << max({d[1].dp[0][0],d[1].dp[0][1],d[1].dp[1][0],d[1].dp[1][1]}) << "\n";
	}
}

Compilation message (stderr)

Main.cpp: In function 'void build(long long int*, long long int, long long int, long long int)':
Main.cpp:36:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |   int mid = l+r>>1;
      |             ~^~
Main.cpp: In function 'void modify(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:51:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |   int mid = l+r>>1;
      |             ~^~

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