#include <iostream>
#include <cmath>
#include<vector>
#include <algorithm>
#include <utility>
#include<stack>
#include<queue>
#include<map>
#include <fstream>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long
#define ans Answer
#define query Query
int a[100010],big[100010],small[100010],smallpos[100010],bigpos[100010];
int tail[100010];
/*bool cmp( int x, int y )
{
if( x > y ) return true;
return false;
}*/
int uupper_bound( int l,int r, int val )
{
int res=0;
int mid=(l+r)/2;
if( tail[mid] > val ){
res=max(res, mid );
l=mid+1;
}
else
r=mid-1;
return res;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,x;
int sol=0;
cin>>n>>x;
for( int i=0;i<n;i++ ){
cin>>a[i+1];
big[i+1]=a[i+1]+x;
small[i+1]=a[i+1]-x;
}
tail[1]=a[1];
int len=2;
bigpos[1] = 1;
bigpos[2]=1;
if( big[2] > a[1] ) bigpos[2]=2; /// valja li ovo
for( int i=2;i<=n;i++ ){
if( a[i] < tail[1] ) tail[1] = a[i];
else if( a[i] > tail[len-1] ) tail[len++]=a[i];
else{
int idx = lower_bound( tail+1, tail+len, a[i] )-tail;
tail[idx]=a[i];
}
// if( i==2 ) cout << len << " " << tail[len-1] << " "<< big[i+1] << " majsta " <<endl;
///provjeriti valja li ova bigpos racunaljka
if( big[i+1] < tail[1] ) bigpos[i+1]=1;
else if(big[i+1] > tail[len-1] ) bigpos[i+1]=len;
else bigpos[i+1] = lower_bound( tail+1, tail+len,big[i+1] )-tail;
} ///izgradili smo regular. smallpos[n-1] i smallpos[n] moram rucno naci, i isto za bigpos
sol=len-1; /// ovo je prvo rjesenje kad ne dodas nista
bigpos[n+1]=0;
for( int i=0;i<len;i++ ) tail[i]=0;
tail[1]=a[n];
len=2;
smallpos[n]=1;
smallpos[n-1] = 1;
if( small[n-1] < a[n] ) smallpos[n-1]=2;
for( int i=n-1;i>=1;i-- ){
if( a[i] > tail[1] ) tail[1]=a[i];
else if( a[i] < tail[len-1] )tail[len++]=a[i];
else{
int idx = lower_bound( tail,tail+len,a[i] )-tail;
idx++; /// dodamo, jer je ovaj iznad idx nemodifikovani, jos kad mu dodamo a[i] bice jos veci len
tail[idx]=a[i];
}
if( i==0 ) break;
if( small[i-1] > tail[1] ) smallpos[i-1] = 1;
else if( small[i-1] < tail[len-1] ) smallpos[i-1]=len;
else{
// if( i==5 ) cout << " kako " << tail[1] << " " <<tail[2] << " " << tail[3] << " " << uupper_bound( 1,len-1,small[i-1] ) <<endl;
// smallpos[i-1]=upper_bound( tail+1,tail+len,small[i-1],cmp )-tail; /// treba li -tail?
smallpos[i-1]=uupper_bound( 1,len-1,small[i-1] ); /// treba li -tail?
smallpos[i-1]++; /// dodamo 1 iz istog razloga ko gore
}
}
/// sad kad imamo smallpos i bigpos, mozemo za small i big isto ici redom po tailove
for( int i=0;i<len;i++ ) tail[i]=0;
tail[1]=small[1];
len=2;
/// sol=max( sol, smallpos[1] ) ; /// mislim da more i ovo
/// trebam skontati kako idu rjesenja kad se sve poveca/smanji
for( int i=2;i<=n;i++ ){
if( small[i] < tail[1] ) tail[1]=small[i];
else if( small[i] > tail[len-1] ) tail[len++]=small[i];
else{
int idx = lower_bound( tail+1,tail+len, small[i] ) - tail;
}
sol = max( sol, len-1 + smallpos[i] - 1 ) ; /// -1 zbog njega samog. len je duzina lijevo, smallpos je desno koliko moze ici. prvo -1 jer len ide unaprijed
}
/// sol=max( sol,len ); /// kad sve smanjis, mada je to isto ko kad ih sve ostavis
/// sol=max( sol, bigpos[n] );
for( int i=0;i<len;i++ ) tail[len]=0;
len=2;
tail[1] = big[1];
for( int i=n-1;i>=1;i-- ){
if( big[i] > tail[1] ) tail[1]=big[i];
else if( big[i] < tail[len-1] ) tail[len++] = big[i];
else{
// int idx = upper_bound( tail+1, tail+len, big[i],cmp )-tail;
int idx = uupper_bound( 1,len-1, big[i] );
idx++;/// poveca se slicno ko iznad
}
sol=max( sol, len-1 + bigpos[i] - 1 );
}
/// jos mi fali da skontam kad sve treba povecat ili smanji, to cu valjda skontat
cout << sol<<endl;
/* for( int i=1;i<=n;i++ ){
cout << i << " "<< smallpos[i] << " " << bigpos[i] <<endl;
}*/
return 0;
}
Compilation message
glo.cpp: In function 'int main()':
glo.cpp:114:21: warning: unused variable 'idx' [-Wunused-variable]
int idx = lower_bound( tail+1,tail+len, small[i] ) - tail;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
4088 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
1912 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
3192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
