제출 #655166

#제출 시각아이디문제언어결과실행 시간메모리
655166ParsaSGlobal Warming (CEOI18_glo)C++14
100 / 100
69 ms6144 KiB
// 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;
}
#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...