Submission #86089

#	Time	Username	Problem	Language	Result	Execution time	Memory
86089		zubec	Global Warming (CEOI18_glo)	C++14	100 / 100	77 ms	37368 KiB

glo

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

const int N = 200100;
const int MAX = 1000000100;

int n, d, pref[N], a[N], mx_posl[N], suff[N];

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);

    cin >> n >> d;
    pref[0] = -MAX;
    for (int i = 1; i <= n; i++){
        pref[i] = MAX;
    }
    int ans = 0;
    for (int i = 1; i <= n; i++){
        int l = 0, r = i;
        cin >> a[i];
        while(l < r){
            int mid = (l+r)>>1;
            if (pref[mid] < a[i])
                l = mid+1; else
                r = mid;
        }
        pref[l] = min(pref[l], a[i]);
        mx_posl[i] = l;
        ans = max(ans, l);
    }
    for (int i = 1; i <= n; i++){
        suff[i] = -MAX;
    }
    suff[n+1] = MAX;
    for (int i = n; i >= 1; i--){
        int l = i, r = n+1;
        while(l < r){
            int mid = (l+r+1)>>1;
            if (suff[mid] > a[i]-d)
                r = mid-1; else
                l = mid;
        }
        ans = max(ans, mx_posl[i]+n-l);
        //cout << i << ' ' << l << ' ' << mx_posl[i]+n-l << ' ';
        l = i, r = n+1;
        while(l < r){
            int mid = (l+r+1)>>1;
            if (suff[mid] > a[i])
                r = mid-1; else
                l = mid;
        }
        //cout <<  l << endl;
        suff[l] = max(suff[l], a[i]);
    }
    cout << ans;

}

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