제출 #636995

#제출 시각아이디문제언어결과실행 시간메모리
636995tvladm2009Global Warming (CEOI18_glo)C++14
100 / 100
274 ms7728 KiB
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2 * 1e5;
int a[MAX_N + 1], dp1[MAX_N + 1], dp2[MAX_N + 1], ind[MAX_N + 1];
pair<int, int> v[MAX_N + 1];
int n, x;

class BIT {
    int aib[MAX_N + 1];

    void update(int p, int val) {
        for (int i = p; i >= 1; i -= i & -i) {
            aib[i] = max(aib[i], val);
        }
    }

    int query(int p) {
        int ans = 0;
        for (int i = p; i <= n; i += i & -i) {
            ans = max(ans, aib[i]);
        }
        return ans;
    }

public:
    void reset() {
        memset(aib, 0, sizeof(aib));
    }

    void update_greater(int x, int val) {
        int p = lower_bound(v + 1, v + n + 1, make_pair(x, 0)) - v;
        update(p, val);
    }

    int query_greater(int x) {
        int p = lower_bound(v + 1, v + n + 1, make_pair(x + 1, 0)) - v;
        return query(p);
    }

    void update_smaller(int x, int val) {
        int p = lower_bound(v + 1, v + n + 1, make_pair(x, 0)) - v;
        update(n - p + 1, val);
    }

    int query_smaller(int x) {
        int p = lower_bound(v + 1, v + n + 1, make_pair(x, 0)) - v - 1;
        return query(n - p + 1);
    }
} aib;

void norm() {
    for (int i = 1; i <= n; i++) {
        v[i] = {a[i], i};
    }
    sort(v + 1, v + n + 1);
    int cnt = 1;
    ind[v[1].second] = cnt;
    for (int i = 2; i <= n; i++) {
        if (v[i].first != v[i - 1].second) {
            cnt++;
        }
        ind[v[i].second] = cnt;
    }
}

void solve() {
    aib.reset();
    for (int i = n; i >= 1; i--) {
        dp2[i] = aib.query_greater(a[i]) + 1;
        aib.update_greater(a[i], dp2[i]);
    }
    int ans = 0;
    aib.reset();
    for (int i = 1; i <= n; i++) {
        int cur = aib.query_smaller(a[i] + x) + dp2[i];
        ans = max(ans, cur);
        dp1[i] = aib.query_smaller(a[i]) + 1;
        aib.update_smaller(a[i], dp1[i]);
    }
    cout << ans << "\n";
}

int main() {
    cin >> n >> x;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    norm();
    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...