Submission #679792

#	Time	Username	Problem	Language	Result	Execution time	Memory
679792		amir	Sjeckanje (COCI21_sjeckanje)	C++17	55 / 110	2053 ms	5136 KiB

Main

/*
<< in the name of Allah >>
*/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll ;
typedef pair<int , int> pii ;
typedef pair<ll , ll> pll ;
#define ps push_back
#define pb pop_back
#define mp make_pair
#define all(x) x.begin() , x.end() 
#define sz(x) (int)x.size() 
#define debug(a) cout<<"debug: "<<(#a)<<" = "<<a<<'\n'
#define debugAr(a) cout << "Array " << (#a) << " :\n" ;for (int TMP : a) cout << TMP << " " ; cout << '\n' ;
const int maxn = 2e5 + 3 ;
ll dp[maxn] ;
ll a[maxn] ;
ll ghol[maxn] ;
ll n , q ;

ll Abs(ll x){
	if (x < 0) x = 0-x ;
	return x ;
}

void solve(){
	fill(ghol , ghol+n+2 , 0 ) ;
	for (int i = n ;i > 1 ; i--){
		if (a[i-1] <= a[i]){
			int j = i-1 ;
			while (a[j] <= a[j+1] && j > 0){
				ghol[j] = i ;
				j-- ;
			}
			i = j+2 ;
		}
		else{
			int j = i-1 ;
			while (a[j] > a[j+1] && j > 0){
				ghol[j] = i ;
				j-- ;
			}
			i = j+2 ;
		}
	}
	for (int i = n-1 ; i > 0 ;i--){
		ll x = Abs(a[ghol[i]] - a[i]) ;
		dp[i] = max(dp[i+1] , (x+dp[ghol[i]+1])) ;
		if (ghol[i] > i){
			x = Abs(a[ghol[i]-1] -a[i]) ;
			dp[i] = max(dp[i] , x+dp[ghol[i]]) ;
		}
	}
	cout << dp[1] << '\n' ;
}


int main()
{
    ios::sync_with_stdio(false) ; 
	cin.tie(NULL) ;
	cout.tie(NULL) ;
	cin>> n >> q ;
	for (int i = 1;i <= n ; i++) cin >> a[i] ;
	while (q--){
		ll l , r , tt ;
		cin >> l >> r >> tt ;
		for (int i = l ; i <= r ; i++) a[i] += tt ;
		solve() ;
	}
	
	
}

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