제출 #876964

#제출 시각아이디문제언어결과실행 시간메모리
876964LudisseyGlobal Warming (CEOI18_glo)C++14
0 / 100
50 ms8292 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

vector<int> a;
vector<int> dpx;
vector<int> dsx;
vector<int> prefx;
vector<int> suffx;

int n,x;

int UPPER_BOUND(int x){
    int l=0,r=n-1;
    while(l<r){
        int mid=(l+r)/2;
        if(dpx[mid]>x){
            r=mid;
        }else l=mid+1;
    }
    return l;
}

signed main() {
	// Input:
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> x;
    a.resize(n);
    dpx.resize(n,1e18);
    dsx.resize(n,1e18);
    prefx.resize(n);
    suffx.resize(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    dpx[0]=-1e18;
    dsx[0]=-1e18;
    for (int i = 0; i < n; i++) {
        int l = upper_bound(dpx.begin(), dpx.end(), a[i]) - dpx.begin();
        if (dpx[l-1] < a[i] && a[i] < dpx[l]) dpx[l] = a[i];
        prefx[i]=l;
    }
    for (int i = n-1; i >= 0; i--) {
        int l = lower_bound(dsx.begin(), dsx.end(), a[i]+x) - dsx.begin();
        suffx[i]=l-1;
        l = lower_bound(dsx.begin(), dsx.end(), a[i]) - dsx.begin();
        if (dsx[l-1] < a[i] && a[i] < dsx[l]) dsx[l] = a[i];
    }
    int ans=-1;
    for (int i = 0; i < n; i++) {
        prefx[i]+=suffx[i];
        ans=max(ans,prefx[i]);
    }
    cout << ans << "\n";

    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...