Submission #1338361

#TimeUsernameProblemLanguageResultExecution timeMemory
1338361i_love_springGlobal Warming (CEOI18_glo)C++20
100 / 100
66 ms3944 KiB
#include <bits/stdc++.h>

using namespace std;

#define ar array
#define ll long long 
const int inf = 2e9;

void solve() {
    int n, d;
    cin >> n >> d;
    vector<int> pref(n + 1, 0), suff(n + 1, 0), a(n + 1);
    for (int i = 1; i <= n;i++) 
        cin >> a[i];

    vector<int> lis;
    for (int i = 1; i <= n;i++) {
        int j = lower_bound(lis.begin(), lis.end(), a[i]) - lis.begin();
        if (j == lis.size()) 
            lis.push_back(a[i]);
        else 
            lis[j] = a[i];
        pref[i] = j + 1;
    }

    vector<int> lds;
    for (int i = n; i >= 1;i--) {
        int j = lower_bound(lds.begin(), lds.end(), -a[i]) - lds.begin();
        if (j == lds.size()) 
            lds.push_back(-a[i]);
        else 
            lds[j] = -a[i];
        suff[i] = j + 1;
    }

    lis.clear();
    lds.clear();


    int ans = pref[n];

    for (int i = 1; i < n;i++) {
        int j = lower_bound(lis.begin(), lis.end(), a[i]) - lis.begin();
        if (j == lis.size()) 
            lis.push_back(a[i]);
        else 
            lis[j] = a[i];
        int x = a[i + 1] + d;
        int y = lower_bound(lis.begin(), lis.end(), x) - lis.begin();
        ans = max(ans, y + suff[i + 1]);
    }

    for (int i = n; i > 1;i--) {
        int j = lower_bound(lds.begin(), lds.end(), -a[i]) - lds.begin();
        if (j == lds.size()) 
            lds.push_back(-a[i]);
        else 
            lds[j] = -a[i];
        int x = a[i - 1] - d;
        int y = lower_bound(lds.begin(), lds.end(), -x) - lds.begin();
        ans = max(ans, y + pref[i - 1]);
    }

    cout << ans << "\n";

}

int32_t main() { 

#ifdef Behruz
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif 

    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    solve();

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