Submission #950082

#	Time	Username	Problem	Language	Result	Execution time	Memory
950082		vjudge1	Sjeckanje (COCI21_sjeckanje)	C++17	0 / 110	34 ms	4444 KiB

Main

//#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 (stderr)

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);}
      |                                                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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