#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
using namespace std;
const int N=3005 ;
long long i,j,n,q,type,l,r,x,ma,mi,lt,rt;
long long a[200005],dp[200005] ;
long long si[4*N],sa[4*N],st[4*N],s[4*N],lzi[4*N],lza[4*N];
pair<int,long long> lz[4*N];
int fi[N], fa[N] ;
deque<int> qq ;
void up(int id, int l, int r, int u, long long x){
if(r<u || u<l) return ;
if(l==r){
s[id]=x ;
return ;
}
int mid=(l+r)/2 ;
up(2*id,l,mid,u,x) ;
up(2*id+1,mid+1,r,u,x) ;
s[id]=max(s[2*id], s[2*id+1]) ;
return ;
}
void fixi(int id, int l, int r){
if(lzi[id]==ma) return ;
si[id]=s[id]-lzi[id] ;
if(l!=r){
lzi[2*id]=lzi[id] ;
lzi[2*id+1]=lzi[id] ;
}
lzi[id]=ma ;
return ;
}
void upi(int id, int l, int r, int u, int v, long long x){
fixi(id,l,r) ;
if(r<u || v<l) return ;
if(u<=l && r<=v){
lzi[id]=x ;
fixi(id,l,r) ;
return ;
}
int mid=(l+r)/2 ;
upi(2*id,l,mid,u,v,x) ;
upi(2*id+1,mid+1,r,u,v,x) ;
si[id]=max(si[2*id], si[2*id+1]) ;
return ;
}
void fixa(int id, int l, int r){
if(lza[id]==ma) return ;
sa[id]=s[id]+lza[id] ;
if(l!=r){
lza[2*id]=lza[id] ;
lza[2*id+1]=lza[id] ;
}
lza[id]=ma ;
return ;
}
void upa(int id, int l, int r, int u, int v, long long x){
fixa(id,l,r) ;
if(r<u || v<l) return ;
if(u<=l && r<=v){
lza[id]=x ;
fixa(id,l,r) ;
return ;
}
int mid=(l+r)/2 ;
upa(2*id,l,mid,u,v,x) ;
upa(2*id+1,mid+1,r,u,v,x) ;
sa[id]=max(sa[2*id], sa[2*id+1]) ;
return ;
}
void fixx(int id,int l, int r,int u, int v,int ii){
if(ii==1) fixa(id,l,r) ;
else fixi(id,l,r) ;
if(l==u && r==v) return ;
int mid=(l+r)/2 ;
if(v<=mid){
fixx(2*id,l,mid,u,v,ii) ;
}else{
fixx(2*id+1,mid+1,r,u,v,ii) ;
}
}
void fix(int id,int l, int r){
if(lz[id].second==ma) return ;
if(lz[id].first==1){
fixx(1,1,n,l,r,1) ;
st[id]=sa[id]-lz[id].second ;
}else{
fixx(1,1,n,l,r,2) ;
st[id]=si[id]+lz[id].second;
}
if(l!=r){
lz[2*id]=lz[id] ;
lz[2*id+1]=lz[id] ;
}
lz[id].second=ma ;
return ;
}
void upd(int id, int l, int r, int u, int v,int ii, long long x){
fix(id,l,r) ;
if(r<u || v<l) return ;
if(u<=l && r<=v){
lz[id]={ii,x} ;
fix(id,l,r) ;
return ;
}
int mid=(l+r)/2 ;
upd(2*id,l,mid,u,v,ii,x) ;
upd(2*id+1,mid+1,r,u,v,ii,x) ;
st[id]=max(st[2*id], st[2*id+1]) ;
return ;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
#define NAME "test"
if(fopen(NAME".inp", "r")){
freopen(NAME".inp", "r", stdin);
freopen(NAME".out", "w", stdout);
}
cin >> n >> q;
for(i=1;i<=n;i++) cin >> a[i] ;
while(q--){
cin >> l >> r >> x ;
for(i=l;i<=r;i++) a[i]+=x ;
ma=-2000000000000000 ;
for(i=0;i<=4*n;i++){
lz[i].second=ma ;
si[i]=ma ;
sa[i]=ma;
st[i]=ma;
s[i]=ma;
lzi[i]=ma;
lza[i]=ma;
}
qq.clear() ;
for(i=1;i<=n;i++){
while(!qq.empty() && a[qq.back()]<=a[i]) qq.pop_back() ;
if(!qq.empty()) fa[i]=qq.back()+1 ;
else fa[i]=1 ;
qq.push_back(i) ;
}
qq.clear() ;
for(i=1; i<=n; i++){
while(!qq.empty() && a[qq.back()]>=a[i]) qq.pop_back() ;
if(!qq.empty()) fi[i]=qq.back()+1 ;
else fi[i]=1 ;
qq.push_back(i) ;
}
dp[0]=0 ;
dp[1]=0 ;
up(1,1,n,1,0) ;
up(1,1,n,2,0) ;
upi(1,1,n,1,1,a[1]) ;
upa(1,1,n,1,1,a[1]) ;
upd(1,1,n,1,1,1,a[1]) ;
for(i=2;i<=n;i++){
//cout << i << ' ' << fa[i] << ' ' << fi[i] << '\n' ;
if(fa[i]!=fi[i]){
if(fa[i]<fi[i]){
lt=fa[i] ;
rt=fi[i] ;
upa(1,1,n,lt,rt-1,a[i]) ;
upd(1,1,n,lt,rt-1,2,a[i]) ;
}else{
lt=fi[i] ;
rt=fa[i] ;
upi(1,1,n,lt,rt-1,a[i]) ;
upd(1,1,n,lt,rt-1,1,a[i]) ;
}
}
upa(1,1,n,i,i,a[i]) ;
upi(1,1,n,i,i,a[i]) ;
upd(1,1,n,i,i,1,a[i]) ;
fix(1,1,n) ;
dp[i]=st[1] ;
//cout << i << ' ' << dp[i] << '\n' ;
up(1,1,n,i+1,dp[i]) ;
}
cout << dp[n] << '\n' ;
}
return 0;
}
/*
4 7
-1 3 -6 8
1 4 4 2
2
1 4 4 3
2
1 1 2 -1
1 1 2 -4
2
*/
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:118:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
118 | freopen(NAME".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:119:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
119 | freopen(NAME".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
22 ms |
2648 KB |
Output is correct |
| 3 |
Correct |
22 ms |
2392 KB |
Output is correct |
| 4 |
Correct |
21 ms |
2392 KB |
Output is correct |
| 5 |
Correct |
21 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
24 ms |
2540 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
22 ms |
2648 KB |
Output is correct |
| 3 |
Correct |
22 ms |
2392 KB |
Output is correct |
| 4 |
Correct |
21 ms |
2392 KB |
Output is correct |
| 5 |
Correct |
21 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
24 ms |
2540 KB |
Output is correct |
| 7 |
Execution timed out |
2055 ms |
2652 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
22 ms |
2648 KB |
Output is correct |
| 3 |
Correct |
22 ms |
2392 KB |
Output is correct |
| 4 |
Correct |
21 ms |
2392 KB |
Output is correct |
| 5 |
Correct |
21 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
24 ms |
2540 KB |
Output is correct |
| 7 |
Execution timed out |
2055 ms |
2652 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
