이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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{
/// i ovdje mora upper ipak
/// int idx = lower_bound( tail,tail+len,a[i] )-tail;
/// MOZDA PROBLEM **************************************************************
int idx = uupper_bound( 1,len-1, a[i] );
// if( idx > 0 && tail[idx-1] == a[i] ) idx--;
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;
tail[idx]=small[i]; /// treba li ++
}
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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |