Submission #291922

#	Time	Username	Problem	Language	Result	Execution time	Memory
291922		ngotienhung	Global Warming (CEOI18_glo)	C++14	100 / 100	66 ms	4640 KiB

glo

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second

using namespace std;

const int maxN = 5e5 + 10;
const int inf = 1e9 + 10;

int n,x;
int a[maxN], ans[maxN], f[maxN];

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(); cout.tie();
    cin >> n >> x;

    f[0] = inf;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
        f[i] = inf;
    }

    int res = 0;
    for(int i = 1; i <= n; ++i){
        int it = lower_bound(f, f + n, a[i]) - f;
        f[it] = a[i];
        ans[i] = it + 1;
        res = max(res, ans[i]);
    }

    f[0] = inf;
    for(int i = 1; i <= n; ++i){
        a[i] = -a[i];
        f[i] = inf;
    }

    for(int i = n; i >= 1; --i){
        int it = lower_bound(f, f + n, a[i] + x) - f;
        int it2 = lower_bound(f, f + n, a[i]) - f;
        f[it2] = a[i];
        res = max(res, it + ans[i]);
    }

    cout << res;
}

• 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