제출 #1125131

#제출 시각아이디문제언어결과실행 시간메모리
1125131ardadutGlobal Warming (CEOI18_glo)C++20
100 / 100
51 ms5824 KiB
#include <bits/stdc++.h>
    
#define ll long long
#define pb push_back
#define endl "\n"
#define vec vector<ll>
#define vecvec vector<vector<ll>>
    
using namespace std;
    
/*#define FileName ""
string Ghhhh = ".in";
string Ghhhhh = ".out";
ifstream Girdi(FileName + Ghhhh);
ofstream Cikti(FileName + Ghhhhh);
#define cin Girdi
#define cout Cikti*/

inline void solve(){

    ll n,x,ans = 0;
    cin >> n >> x;
    vector<ll> temps(n);
    vector<ll> prefix_lis(n);

    for(ll i = 0 ; i < n ; i++) cin >> temps[i];

    vector<ll> lis;
    for(ll i = 0 ; i < n ; i++){
        ll j = lower_bound(lis.begin(),lis.end(),temps[i]) - lis.begin();
        if(j == lis.size()) lis.pb(temps[i]);
        else lis[j] = temps[i];
        prefix_lis[i] = j+1;
        ans = max(ans,prefix_lis[i]);
    }

    vector<ll> lis2;
    for(ll i = n-1 ; i >= 0 ; i--){
        ll pos = lower_bound(lis2.begin(),lis2.end(),-temps[i]+x) - lis2.begin();
        ans = max(ans,prefix_lis[i] + pos);

        ll j = lower_bound(lis2.begin(),lis2.end(),-temps[i]) - lis2.begin();
        if(j == lis2.size()) lis2.pb(-temps[i]);
        else lis2[j] = -temps[i];
    }

    cout << ans << endl;

}
    
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    
}
#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...