제출 #361647

#제출 시각아이디문제언어결과실행 시간메모리
361647iliccmarkoGlobal Warming (CEOI18_glo)C++14
45 / 100
64 ms4588 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define endl "\n" #define INF 1000000000 #define LINF 1000000000000000LL #define pb push_back #define all(x) x.begin(), x.end() #define len(s) (int)s.size() #define test_case { int t; cin>>t; while(t--)solve(); } #define single_case solve(); #define line cerr<<"----------"<<endl; #define ios { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cerr.tie(NULL); } #define mod 1000000007LL const int N = 2e5 + 5; int a[N], dp[N], levo[N], desno[N]; int n, x; int main() { ios cin>>n>>x; for(int i = 0;i<n;i++) cin>>a[i]; for(int i = 0;i<N;i++) dp[i] = INF; for(int i = 0;i<n;i++) { int pos = lower_bound(dp, dp+n+1, a[i]+x) - dp; levo[i] = pos-1; pos = lower_bound(dp+1, dp+n+1, a[i]) - dp; //cout<<pos<<endl; dp[pos] = a[i]; } for(int i = 0;i<N;i++) dp[i] = INF; int ans = 0; for(int i = n-1;i>=0;i--) { int pos = lower_bound(dp+1, dp+n+1, -a[i]) - dp; dp[pos] = -a[i]; //cout<<levo[i]<<" "<<pos<<endl; ans = max(ans, levo[i]+pos); } cout<<ans; return 0; }
#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...