Submission #952562

#	Time	Username	Problem	Language	Result	Execution time	Memory
952562		Sundavar	Global Warming (CEOI18_glo)	C++14	100 / 100	104 ms	5484 KiB

glo

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,d;
    cin>>n>>d;
    vector<int> v(n);
    for(int& a : v) cin>>a;
    vector<int> smallest(n+1, 1e9+7), here(n);
    smallest[0] = 0;
    for(int i = 0; i < n; i++){
        int l = lower_bound(smallest.begin(), smallest.end(), v[i]) - smallest.begin();
        here[i] = l;
        smallest[l] = v[i];
    }
    vector<int> biggest(n+1, -(1e9+7));
    biggest[0] = 1e9+7;
    int sol = 0;
    for(int i = n-1; i >= 0; i--){
        int l = 0, r = n;
        while(r-l > 1)
            if(biggest[(r+l)/2] > v[i]-d) l = (l+r)/2;
            else r = (l+r)/2;
        sol = max(sol, l+here[i]);
        l = 0, r = n;
        while(r-l > 1)
            if(biggest[(r+l)/2] > v[i]) l = (l+r)/2;
            else r = (l+r)/2;
        biggest[l+1] = v[i];
    }
    cout << sol << "\n";
}

• 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