Submission #1048983

#TimeUsernameProblemLanguageResultExecution timeMemory
1048983matereGlobal Warming (CEOI18_glo)C++14
62 / 100
79 ms8144 KiB
#include<bits/stdc++.h> using namespace std; pair<long long,long long>step[200005]; long long a[200005],d[200005],dc[200005],ls; int main(){ long long n,x; cin>>n>>x; d[0]=-2e9-1; for(long long i=1;i<=n;i++) d[i]=2e9+1; for(long long i=1;i<=n;i++){ cin>>a[i]; long long l=0,r=n+1; while(l+1<r){ long long mid=(l+r)/2; if(d[mid]<a[i]) l=mid; else r=mid; } l++; if(d[l]>a[i]){ step[i]={l,d[l]}; d[l]=a[i]; ls=max(ls,l); } } d[n+1]=2e9+1; long long ans=ls,ld=0; dc[0]=2e9+1; for(long long i=1;i<=n;i++) dc[i]=-2e9-1; for(long long i=n;i>=1;i--){ if(step[i].first!=0){ d[step[i].first]=step[i].second; if(d[step[i].first]==2e9+1) ls--; } a[i]+=x; long long l=0,r=n+1; while(l+1<r){ long long mid=(l+r)/2; if(dc[mid]>a[i]) l=mid; else r=mid; } l++; if(dc[l]<a[i]){ dc[l]=a[i]; ld=max(ld,l); } l=0,r=n+1; while(l+1<r){ long long mid=(l+r)/2; if(dc[mid]>d[ls]) l=mid; else r=mid; } ans=max(ans,ls+l); } cout<<ans<<endl; }
#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...