Submission #940143

#	Time	Username	Problem	Language	Result	Execution time	Memory
940143		Cutebol	Global Warming (CEOI18_glo)	C++17	17 / 100	311 ms	28328 KiB

glo

#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 long long
#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 = 1e16 ;
const int mod = 1e9 + 8 ;
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 , k , ans ;
int a[N] , p[N] , s[N] , g[N*4] ;

void build ( int v , int l , int r ){
	g[v] = 0 ;
	if ( l == r ) return ;
	int m = ( l + r ) / 2 ;
	build ( v+v , l , m ) ;
	build ( v+v+1 , m+1 , r ) ;
}

int get ( int v , int l , int r , int tl , int tr ){
	if ( l > tr || r < tl ) return 0 ;
	if ( l >= tl && r <= tr ) return g[v] ;
	int m = ( l + r ) / 2 ;
	return max ({ get ( v+v , l , m , tl , tr ) , get ( v+v+1 , m+1 , r , tl , tr )}) ;
}

void add ( int v , int l , int r , int x , int a ){
	chmax ( g[v] , a ) ;
	if ( l == r ) return ;
	int m = ( l + r ) / 2 ;
	if ( x <= m ) add ( v+v , l , m , x , a ) ;
	else add ( v+v+1 , m+1 , r , x , a ) ;
}
vector <int> vec ;
map <int , int> mp ;
int d[N] ;
void solve(){
	cin >> n >> k ;
	for ( int i = 1 ; i <= n ; i ++ ) cin >> a[i] ;
	for ( int i = 1 ; i <= n ; i ++ ) vec.push_back(a[i]) ;
	sort ( all(vec) ) ; int x = 1 ; mp[0] = 1 ;
	for ( int i = 1 ; i < n ; i ++ ){
		if ( vec[i] != vec[i-1] ) x ++ ;
		mp[vec[i]] = x ;
	} int ind = n-1 ;
	for ( int i = n-1 ; i >= 0 ; i -- ){
		while ( ind >= 0 && vec[i]-k < vec[ind] ) ind -- ;
		if ( i != ind )ind ++ ;
		d[mp[vec[i]]] = mp[vec[ind]] + ( vec[ind] == vec[i] ) ;
	}
	for ( int i = 1 ; i <= n ; i ++ ) a[i] = mp[a[i]] ;
	for ( int i = 1 ; i <= n ; i ++ ){
		p[i] = get( 1 , 1 , x , 1 , a[i]-1 ) + 1 ;
		add ( 1 , 1 , x , a[i] , p[i] ) ;
	} build ( 1 , 1 , x ) ; reverse ( a+1 , a+n+1 ) ;
	for ( int i = 1 ; i <= n ; i ++ ){
		s[i] = get ( 1 , 1 , x , a[i]+1 , x ) + 1 ;
		add( 1 , 1 , x , a[i] , s[i] ) ;
	} reverse ( a+1 , a+n+1 ) ; reverse ( s+1 , s+n+1 ) ;
	build ( 1 , 1 , x ) ; ans = p[n] ; add ( 1 , 1 , n , a[n] , s[n] ) ;
	if ( !k ){
		cout << ans ;
		return ;
	}
	for ( int i = n-1 ; i > 0 ; i -- ){
		chmax ( ans , get ( 1 , 1 , n , d[a[i]] , x ) + p[i] ) ;
		add ( 1 , 1 , n , a[i] , s[i] ) ;
	}
	cout << ans ;
}

signed main(){
    ios ;
	int t = 1 ;
	//cin >> t ;
	while ( t -- ) solve() ;
}

Compilation message (stderr)

glo.cpp: In function 'void fopn(std::string)':
glo.cpp:10:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
glo.cpp:10:72: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                                                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 20
• Subtask 6: 17 / 17
• Subtask 7: 0 / 25