제출 #128435

#제출 시각아이디문제언어결과실행 시간메모리
128435OptxPrimeGlobal Warming (CEOI18_glo)C++11
0 / 100
26 ms4088 KiB
#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; }

컴파일 시 표준 에러 (stderr) 메시지

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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...