제출 #1322576

#제출 시각아이디문제언어결과실행 시간메모리
1322576ttamxGlobal Warming (CEOI18_glo)C++17
100 / 100
46 ms2496 KiB
#include<bits/stdc++.h> using namespace std; const int N=2e5+5; int n,x; int a[N]; int dpr[N]; int main(){ cin.tie(nullptr)->sync_with_stdio(false); cin >> n >> x; for(int i=1;i<=n;i++){ cin >> a[i]; } vector<int> lis; for(int i=n;i>=1;i--){ int idx=lower_bound(lis.begin(),lis.end(),-a[i])-lis.begin(); dpr[i]=idx+1; if(idx==lis.size())lis.push_back(-a[i]); else lis[idx]=-a[i]; } lis.clear(); int ans=0; for(int i=1;i<=n;i++){ int idx=lower_bound(lis.begin(),lis.end(),a[i]+x)-lis.begin(); ans=max(ans,dpr[i]+idx); idx=lower_bound(lis.begin(),lis.end(),a[i])-lis.begin(); if(idx==lis.size())lis.push_back(a[i]); else lis[idx]=a[i]; } cout << ans << "\n"; }
#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...