/*
<< 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 = 3e3 + 3 ;
ll dp[maxn] ;
ll a[maxn] ;
int ghol[maxn] ;
ll n , q ;
ll Abs(ll x){
if (x < 0) x = 0-x ;
return x ;
}
void solve(){
//for (int i = 1; i <= n ; i++) cout << a[i] << " " ;
//cout << '\n' ;
if (a[n] >= a[n-1]){
int j = n-1 ;
while (a[j] <= a[n] && j > 0){
ghol[j] = n ;
j-- ;
}
}
else if (a[n] <= a[n-1]){
int j = n-1 ;
while (a[j] <= a[n] && j > 0){
ghol[j] = n ;
j-- ;
}
}
for (int i = n-1 ; i > 1 ; i--){
if (a[i] >= a[i-1] && a[i] > a[i+1]){
int j = i-1 ;
while (a[j] <= a[i] && j > 0){
ghol[j] = i ;
j-- ;
}
}
else if (a[i] <= a[i-1] && a[i] < a[i+1]){
int j = i-1 ;
while (a[j] >= a[i] && j > 0){
ghol[j] = i ;
j-- ;
}
}
}
//for (int i = 1; i <= n ; i++) cout << ghol[i] << " " ;
//cout << '\n' ;
dp[n] = 0 ;
dp[n+1] = 0 ;
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){
ll y = Abs(a[ghol[i]-1]-a[i]) ;
dp[i] = max(dp[i] , (y+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--){
int l , r , x ;
cin >> l >> r >> x ;
for (int i = l ;i <= r ; i++) a[i] += x ;
solve() ;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
