oj.uz

Submission #940109

# Submission time Handle Problem Language Result Execution time Memory
940109 2024-03-07T05:40:28 Z vjudge1 Global Warming (CEOI18_glo) C++17
37 / 100
 294 ms 37572 KB 
#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 ; mp[0] = 1 ;
	for ( int i = n-1 ; i >= 0 ; i -- ){
		while ( ind >= 0 && vec[i]-k < vec[ind] ) ind -- ;
		ind ++ ;
		d[mp[vec[i]]] = mp[vec[ind]] ;
	}
	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] ) ;
	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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 8792 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 2 ms 8536 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Incorrect 1 ms 8540 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 8792 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 2 ms 8536 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Incorrect 1 ms 8540 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 8792 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 2 ms 8536 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Incorrect 1 ms 8540 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 83 ms 37572 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 12496 KB Output is correct
2 Correct 70 ms 12496 KB Output is correct
3 Correct 66 ms 12492 KB Output is correct
4 Correct 35 ms 10708 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 46 ms 10804 KB Output is correct
7 Correct 62 ms 12492 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 17100 KB Output is correct
2 Correct 132 ms 17356 KB Output is correct
3 Correct 294 ms 26312 KB Output is correct
4 Correct 148 ms 19120 KB Output is correct
5 Correct 91 ms 17084 KB Output is correct
6 Correct 160 ms 25652 KB Output is correct
7 Correct 164 ms 25544 KB Output is correct
8 Correct 118 ms 17172 KB Output is correct

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 8792 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 2 ms 8536 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Incorrect 1 ms 8540 KB Output isn't correct
9 Halted 0 ms 0 KB -