Submission #950040

#	Time	Username	Problem	Language	Result	Execution time	Memory
950040		vjudge1	Sjeckanje (COCI21_sjeckanje)	C++17	55 / 110	2029 ms	6484 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false); cin.tie(NULL);
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fr first
#define sc second
#define mp make_pair
#define ll long long
const ll INF=1e18,N=2e5+5;
void solve(){
	int n,q;cin>>n>>q;
	vector<ll> a(n+1);
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	vector<ll> dp(n),prv(n);
	while(q--){
		int l,r,x;cin>>l>>r>>x;
		
		for(int i=l;i<=r;i++) a[i]+=x;
		dp[1]=0;
		dp[2]=abs(a[2]-a[1]);
		prv[2]=1;
		for(int i=3;i<=n;i++){
			dp[i]=dp[i-1];
			if((a[i]>=a[i-1]) == (a[i-1]>=a[i-2])) prv[i]=prv[i-1];
			
			else prv[i]=i-1;
			dp[i]=max(dp[i],abs(a[i]-a[prv[i]])+dp[prv[i]-1]);
			dp[i]=max(dp[i],abs(a[i]-a[prv[i]+1])+dp[prv[i]]);
		}
		cout<<dp[n]<<endl;
	}
}
int main(){
	solve();
}

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