Submission #876964

#	Time	Username	Problem	Language	Result	Execution time	Memory
876964		Ludissey	Global Warming (CEOI18_glo)	C++14	0 / 100	50 ms	8292 KiB

glo

#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;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25