// NgJaBach: Forever Meadow <3
#include<bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long int ll;
typedef unsigned long long ull;
#define pb push_back
#define pob pop_back
#define mp make_pair
#define upb upper_bound
#define lwb lower_bound
#define bend(a) a.begin(),a.end()
#define rev(x) reverse(bend(x))
#define mset(a) memset(a, 0, sizeof(a))
#define fi first
#define se second
#define gcd __gcd
#define getl(s) getline(cin, s);
#define setpre(x) fixed << setprecision(x)
#define endl '\n'
const int N=200050,M=1000000007;
const ll INF=1e18+7;
struct ask{
int x,y;
ll z;
};
ll arr[N];
int q,n;
vector<ask>queries;
namespace sub1{
ll a[205],dp[205],minis[205][205],maxis[205][205];
vector<ll>ans;
vector<ll>solve(){
ans.clear();
int x,y; ll z;
for(int i=1;i<=n;++i) a[i]=arr[i];
for(int t=0;t<q;++t){
x=queries[t].x; y=queries[t].y; z=queries[t].z;
for(int i=x;i<=y;++i) a[i]+=z;
for(int i=1;i<=n;++i){
maxis[i][i]=a[i];
minis[i][i]=a[i];
for(int j=i+1;j<=n;++j){
maxis[i][j]=max(maxis[i][j-1],a[j]);
minis[i][j]=min(minis[i][j-1],a[j]);
}
}
dp[0]=0;
for(int i=1;i<=n;++i){
dp[i]=-INF;
for(int j=1;j<=i;++j) dp[i]=max(dp[i],dp[j-1]+maxis[j][i]-minis[j][i]);
}
ans.pb(dp[n]);
}
return ans;
}
}
namespace sub2{
ll a[3005],dp[3005][2],d[3005];
vector<ll>ans;
vector<ll>solve(){
ans.clear();
int x,y; ll z;
for(int i=1;i<=n;++i) a[i]=arr[i];
for(int t=0;t<q;++t){
x=queries[t].x; y=queries[t].y; z=queries[t].z;
for(int i=x;i<=y;++i) a[i]+=z;
for(int i=1;i<n;++i) d[i]=a[i]-a[i+1];
dp[0][0]=0; dp[0][1]=0; d[n]=0;
for(int i=1;i<=n;++i){
dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
dp[i][1]=dp[i-1][0];
if(d[i]*d[i-1]>=0) dp[i][1]=max(dp[i][1],dp[i-1][1]+abs(d[i]));
else dp[i][1]=max(dp[i][1],dp[i-2][1]+abs(d[i]));
}
// cout<<"a: "; for(int i=1;i<=n;++i) cout<<a[i]<<" "; cout<<endl;
// cout<<"d: "; for(int i=1;i<=n;++i) cout<<d[i]<<" "; cout<<endl;
// cout<<"dp"<<endl;
// for(int j=0;j<2;++j) for(int i=1;i<=n;++i) cout<<dp[i][j]<<" "; cout<<endl;
ans.pb(max(dp[n-1][0],dp[n-1][1]));
}
return ans;
}
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
// freopen("RECIPE.inp","r",stdin);
// freopen("RECIPE.out","w",stdout);
cin>>n>>q;
for(int i=1;i<=n;++i) cin>>arr[i];
for(int i=0;i<q;++i){
int x,y,z;
cin>>x>>y>>z;
queries.pb({x,y,z});
}
vector<ll>ans;
// if(n<=200 and q<=200) ans=sub1::solve();
// else if(n<=3000 and q<=3000)
ans=sub2::solve();
for(ll &tmp:ans) cout<<tmp<<endl;
return 0;
}
/*
==================================+
INPUT: |
------------------------------ |
------------------------------ |
==================================+
OUTPUT: |
------------------------------ |
------------------------------ |
==================================+
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
