//#pragma GCC optimizer("03") ;
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
bool YES(bool f){ if(f) cout << "Yes\n" ; else cout << "No\n" ; return f ; }
void YES(){YES(1);}
void NO(){YES(0);}
void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
//#define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ios ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0);
//#define int unsigned short
#define ld long double
#define pii pair <int , int>
#define all(x) x.begin() , x.end()
#define ff first
#define ss second
#define endl '\n'
const int N = 2e5 + 5 ;
const int inf = 1e9 ;
const int mod = 1e9 + 7 ;
const double eps = 1e-8 ;
template <class T>
bool chmax( T& x , const T& y ){
bool f = 0 ;
if ( x < y ) x = y , f = 1 ;
return f ;
}
template <class T>
bool chmin( T &x , const T &y ){
bool f = 0 ;
if ( x > y ) x = y , f = 1 ;
return f ;
}
//code
int n , a[N] , ans , q ;
int gm[N*4] , gx[N*4] , g[N*4] ;
void build ( int v , int l , int r ){
if ( l == r ){
gm[v] = a[l] ;
gx[v] = a[l] ;
return ;
}
int m = ( l + r ) / 2 ;
build ( v+v , l , m ) ;
build ( v+v+1 , m+1 , r ) ;
gx[v] = max ( gx[v+v] , gx[v+v+1] ) ;
gm[v] = min ( gm[v+v] , gm[v+v+1] ) ;
}
void push ( int v ){
g[v+v] += g[v] ;
g[v+v+1] += g[v] ;
gx[v] += g[v] ;
gm[v] += g[v] ;
g[v] = 0 ;
}
void add ( int v , int l , int r , int tl , int tr , int x ){
if ( l > tr || r < tl ) return ;
if ( l >= tl && r <= tr ){
g[v] += x ;
push(v) ;
return ;
} int m = ( l + r ) / 2 ;
push(v) ;
add ( v+v , l , m , tl , tr , x ) ;
add ( v+v+1 , m+1 , r , tl , tr , x ) ;
gx[v] = max ( gx[v+v] , gx[v+v+1] ) ;
gm[v] = min ( gm[v+v] , gm[v+v+1] ) ;
}
int getx ( int v , int l , int r , int tl , int tr ){
if ( l > tr || r < tl ) return 0 ;
push(v) ;
if ( l >= tl && r <= tr ) return gx[v] ;
int m = ( l + r ) / 2 ;
return max ( getx( v+v , l , m , tl , tr ) , getx( v+v+1 , m+1 , r , tl ,tr ) ) ;
}
int getm ( int v , int l , int r , int tl , int tr ){
if ( l > tr || r < tl ) return inf ;
push(v) ;
if ( l >= tl && r <= tr ) return gm[v] ;
int m = ( l + r ) / 2 ;
return min ( getm( v+v , l , m , tl , tr ) , getm( v+v+1 , m+1 , r , tl ,tr ) ) ;
}
set <pii> st ;
set <int> ind ;
void solve(){
cin >> n >> q ;
for ( int i = 1 ; i <= n ; i ++ ) cin >> a[i] ;
for ( int i = 2 ; i <= n ; i ++ ) st.insert({abs(a[i]-a[i-1]),i}) ;
ind.insert(1) ;
ind.insert(n+1) ;
build ( 1 , 1 , n ) ;
int ans = getx ( 1 , 1 , n , 1 , n ) - getm ( 1 , 1 , n , 1 , n ) ;
for ( auto it : st ){
auto f = ind.lower_bound( it.ss ) ;
auto s = f ; s -- ;
int old = getx ( 1 , 1 , n , *f , *s-1 ) - getm ( 1 , 1 , n , *f , *s-1 ) ;
int nw = getx( 1 , 1 , n , *f , it.ss-1 ) - getm ( 1 , 1 , n , *f , it.ss-1 ) ;
nw += getx ( 1 , 1 , n , it.ss , *s-1 ) - getm ( 1 , 1 , n , it.ss , *s-1 ) ;
if ( nw > old ){
ans -= old ;
ans += nw ;
ind.insert(it.ss) ;
}
}
for ( int i = 0 ; i < q ; i ++ ){
int l , r , x ; cin >> l >> r >> x ;
if ( l > 1 )st.erase({abs(getx(1,1,n,l,l)-getx(1,1,n,l-1,l-1)),l}) ;
if ( r < n )st.erase({abs(getx(1,1,n,r+1,r+1)-getx(1,1,n,r,r)),r+1}) ;
add ( 1 , 1 , n , l , r , x ) ;
if ( l > 1 )st.insert({abs(getx(1,1,n,l,l)-getx(1,1,n,l-1,l-1)),l}) ;
if ( r < n )st.insert({abs(getx(1,1,n,r+1,r+1)-getx(1,1,n,r,r)),r+1}) ;
ind.clear() ; ans = getx (1,1,n,1,n)-getm(1,1,n,1,n) ;
ind.insert(1) ;
ind.insert(n+1) ;
for ( auto it : st ){
//cout << it.ff << ' ' << it.ss << endl ;
auto s = ind.lower_bound( it.ss ) ;
auto f = s ; f -- ;
//cout << *f << ' ' << *s << endl ;
int old = getx ( 1 , 1 , n , *f , *s-1 ) - getm ( 1 , 1 , n , *f , *s-1 ) ;
int nw = getx( 1 , 1 , n , *f , it.ss-1 ) - getm ( 1 , 1 , n , *f , it.ss-1 ) ;
nw += getx ( 1 , 1 , n , it.ss , *s-1 ) - getm ( 1 , 1 , n , it.ss , *s-1 ) ;
//cout << old << ' ' << nw << endl ;
if ( nw > old ){
//cout << "taking " << it.ff << ' ' << it.ss << endl ;
ans -= old ;
ans += nw ;
ind.insert(it.ss) ;
}
} cout << ans << endl ;
}
}
signed main(){
ios ;
int t = 1 ;
//cin >> t ;
while ( t -- ) solve() ;
}
Compilation message
Main.cpp: In function 'void fopn(std::string)':
Main.cpp:11:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
11 | void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:11:72: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
11 | void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
