Submission #655166

#	Time	Username	Problem	Language	Result	Execution time	Memory
655166		ParsaS	Global Warming (CEOI18_glo)	C++14	100 / 100	69 ms	6144 KiB

glo

// In the name of God
#pragma GCC optimize("O2", "unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
typedef long long ll;
const int N = 2e5 + 5, inf = 2e9 + 5;
int n, x, a[N];
int R[N], L[N];
pair<int, int> p[N];

void solve() {
    cin >> n >> x;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    fill(R, R + N, -inf);
    R[0] = inf;
    for (int i = n - 1; i >= 0; i--) {
        int l = 0, r = N - 1;
        while (r - l > 1) {
            int mid = (l + r) >> 1;
            if (R[mid] > a[i])
                l = mid;
            else
                r = mid;
        }
        p[i] = make_pair(r, R[r]);
        R[r] = a[i];
    }
    int ans = 0;
    fill(L + 1, L + N, inf);
    for (int i = 0; i < n; i++) {
        R[p[i].fi] = p[i].se;

        int j = lower_bound(L, L + N, a[i]) - L;
        L[j] = a[i]; 

        int l = 0, r = N - 1;
        while (r - l > 1) {
            int mid = (l + r) >> 1;
            if (R[mid] + x > a[i])
                l = mid;
            else
                r = mid;
        }
        ans = max(ans, j + l);
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

• 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