#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]) ;
vec.push_back(inf) ;
sort ( all(vec) ) ; int x = 1 ; mp[vec[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 -- ;
ind ++ ;
d[mp[vec[i]]] = mp[vec[ind]] ;
} x ++ ;
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);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
8540 KB |
Output is correct |
2 |
Correct |
2 ms |
8540 KB |
Output is correct |
3 |
Correct |
1 ms |
8540 KB |
Output is correct |
4 |
Correct |
1 ms |
8540 KB |
Output is correct |
5 |
Correct |
1 ms |
8540 KB |
Output is correct |
6 |
Correct |
1 ms |
8540 KB |
Output is correct |
7 |
Correct |
1 ms |
8536 KB |
Output is correct |
8 |
Correct |
1 ms |
8540 KB |
Output is correct |
9 |
Correct |
1 ms |
8540 KB |
Output is correct |
10 |
Correct |
2 ms |
8540 KB |
Output is correct |
11 |
Correct |
1 ms |
8540 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
8540 KB |
Output is correct |
2 |
Correct |
2 ms |
8540 KB |
Output is correct |
3 |
Correct |
1 ms |
8540 KB |
Output is correct |
4 |
Correct |
1 ms |
8540 KB |
Output is correct |
5 |
Correct |
1 ms |
8540 KB |
Output is correct |
6 |
Correct |
1 ms |
8540 KB |
Output is correct |
7 |
Correct |
1 ms |
8536 KB |
Output is correct |
8 |
Correct |
1 ms |
8540 KB |
Output is correct |
9 |
Correct |
1 ms |
8540 KB |
Output is correct |
10 |
Correct |
2 ms |
8540 KB |
Output is correct |
11 |
Correct |
1 ms |
8540 KB |
Output is correct |
12 |
Correct |
1 ms |
8540 KB |
Output is correct |
13 |
Correct |
1 ms |
8540 KB |
Output is correct |
14 |
Correct |
1 ms |
8536 KB |
Output is correct |
15 |
Correct |
1 ms |
8540 KB |
Output is correct |
16 |
Correct |
1 ms |
8536 KB |
Output is correct |
17 |
Correct |
1 ms |
8540 KB |
Output is correct |
18 |
Correct |
1 ms |
8540 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
8540 KB |
Output is correct |
2 |
Correct |
2 ms |
8540 KB |
Output is correct |
3 |
Correct |
1 ms |
8540 KB |
Output is correct |
4 |
Correct |
1 ms |
8540 KB |
Output is correct |
5 |
Correct |
1 ms |
8540 KB |
Output is correct |
6 |
Correct |
1 ms |
8540 KB |
Output is correct |
7 |
Correct |
1 ms |
8536 KB |
Output is correct |
8 |
Correct |
1 ms |
8540 KB |
Output is correct |
9 |
Correct |
1 ms |
8540 KB |
Output is correct |
10 |
Correct |
2 ms |
8540 KB |
Output is correct |
11 |
Correct |
1 ms |
8540 KB |
Output is correct |
12 |
Correct |
1 ms |
8540 KB |
Output is correct |
13 |
Correct |
1 ms |
8540 KB |
Output is correct |
14 |
Correct |
1 ms |
8536 KB |
Output is correct |
15 |
Correct |
1 ms |
8540 KB |
Output is correct |
16 |
Correct |
1 ms |
8536 KB |
Output is correct |
17 |
Correct |
1 ms |
8540 KB |
Output is correct |
18 |
Correct |
1 ms |
8540 KB |
Output is correct |
19 |
Correct |
2 ms |
8540 KB |
Output is correct |
20 |
Correct |
2 ms |
8668 KB |
Output is correct |
21 |
Correct |
2 ms |
8540 KB |
Output is correct |
22 |
Correct |
2 ms |
8792 KB |
Output is correct |
23 |
Correct |
2 ms |
8660 KB |
Output is correct |
24 |
Correct |
2 ms |
8540 KB |
Output is correct |
25 |
Correct |
2 ms |
8540 KB |
Output is correct |
26 |
Correct |
2 ms |
8540 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
338 ms |
26276 KB |
Output is correct |
2 |
Correct |
338 ms |
26372 KB |
Output is correct |
3 |
Correct |
341 ms |
26276 KB |
Output is correct |
4 |
Correct |
346 ms |
26204 KB |
Output is correct |
5 |
Correct |
174 ms |
18888 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
65 ms |
12496 KB |
Output is correct |
2 |
Correct |
69 ms |
12624 KB |
Output is correct |
3 |
Correct |
66 ms |
12724 KB |
Output is correct |
4 |
Correct |
35 ms |
10712 KB |
Output is correct |
5 |
Correct |
1 ms |
8540 KB |
Output is correct |
6 |
Correct |
44 ms |
10808 KB |
Output is correct |
7 |
Correct |
57 ms |
12572 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
139 ms |
17496 KB |
Output is correct |
2 |
Correct |
135 ms |
17108 KB |
Output is correct |
3 |
Correct |
312 ms |
26312 KB |
Output is correct |
4 |
Correct |
153 ms |
19256 KB |
Output is correct |
5 |
Correct |
83 ms |
17104 KB |
Output is correct |
6 |
Correct |
178 ms |
25536 KB |
Output is correct |
7 |
Correct |
165 ms |
25644 KB |
Output is correct |
8 |
Correct |
104 ms |
17200 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
8540 KB |
Output is correct |
2 |
Correct |
2 ms |
8540 KB |
Output is correct |
3 |
Correct |
1 ms |
8540 KB |
Output is correct |
4 |
Correct |
1 ms |
8540 KB |
Output is correct |
5 |
Correct |
1 ms |
8540 KB |
Output is correct |
6 |
Correct |
1 ms |
8540 KB |
Output is correct |
7 |
Correct |
1 ms |
8536 KB |
Output is correct |
8 |
Correct |
1 ms |
8540 KB |
Output is correct |
9 |
Correct |
1 ms |
8540 KB |
Output is correct |
10 |
Correct |
2 ms |
8540 KB |
Output is correct |
11 |
Correct |
1 ms |
8540 KB |
Output is correct |
12 |
Correct |
1 ms |
8540 KB |
Output is correct |
13 |
Correct |
1 ms |
8540 KB |
Output is correct |
14 |
Correct |
1 ms |
8536 KB |
Output is correct |
15 |
Correct |
1 ms |
8540 KB |
Output is correct |
16 |
Correct |
1 ms |
8536 KB |
Output is correct |
17 |
Correct |
1 ms |
8540 KB |
Output is correct |
18 |
Correct |
1 ms |
8540 KB |
Output is correct |
19 |
Correct |
2 ms |
8540 KB |
Output is correct |
20 |
Correct |
2 ms |
8668 KB |
Output is correct |
21 |
Correct |
2 ms |
8540 KB |
Output is correct |
22 |
Correct |
2 ms |
8792 KB |
Output is correct |
23 |
Correct |
2 ms |
8660 KB |
Output is correct |
24 |
Correct |
2 ms |
8540 KB |
Output is correct |
25 |
Correct |
2 ms |
8540 KB |
Output is correct |
26 |
Correct |
2 ms |
8540 KB |
Output is correct |
27 |
Correct |
338 ms |
26276 KB |
Output is correct |
28 |
Correct |
338 ms |
26372 KB |
Output is correct |
29 |
Correct |
341 ms |
26276 KB |
Output is correct |
30 |
Correct |
346 ms |
26204 KB |
Output is correct |
31 |
Correct |
174 ms |
18888 KB |
Output is correct |
32 |
Correct |
65 ms |
12496 KB |
Output is correct |
33 |
Correct |
69 ms |
12624 KB |
Output is correct |
34 |
Correct |
66 ms |
12724 KB |
Output is correct |
35 |
Correct |
35 ms |
10712 KB |
Output is correct |
36 |
Correct |
1 ms |
8540 KB |
Output is correct |
37 |
Correct |
44 ms |
10808 KB |
Output is correct |
38 |
Correct |
57 ms |
12572 KB |
Output is correct |
39 |
Correct |
139 ms |
17496 KB |
Output is correct |
40 |
Correct |
135 ms |
17108 KB |
Output is correct |
41 |
Correct |
312 ms |
26312 KB |
Output is correct |
42 |
Correct |
153 ms |
19256 KB |
Output is correct |
43 |
Correct |
83 ms |
17104 KB |
Output is correct |
44 |
Correct |
178 ms |
25536 KB |
Output is correct |
45 |
Correct |
165 ms |
25644 KB |
Output is correct |
46 |
Correct |
104 ms |
17200 KB |
Output is correct |
47 |
Correct |
150 ms |
18112 KB |
Output is correct |
48 |
Correct |
140 ms |
18108 KB |
Output is correct |
49 |
Correct |
351 ms |
28200 KB |
Output is correct |
50 |
Correct |
162 ms |
20164 KB |
Output is correct |
51 |
Correct |
140 ms |
19680 KB |
Output is correct |
52 |
Correct |
213 ms |
27592 KB |
Output is correct |
53 |
Correct |
190 ms |
27884 KB |
Output is correct |
54 |
Correct |
181 ms |
28136 KB |
Output is correct |
55 |
Correct |
290 ms |
28356 KB |
Output is correct |