제출 #1356119

#제출 시각아이디문제언어결과실행 시간메모리
1356119fgggGlobal Warming (CEOI18_glo)C++20
100 / 100
196 ms33324 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct st {
    vector<ll> t;
    st(ll n) {
        t.assign(4 * n, 0);
    }
    void upd(ll v, ll l, ll r, ll i, ll x) {
        if (l + 1 == r) {
            t[v] = max(t[v], x);
            return;
        }
        ll md = (l + r) / 2;
        if (i < md) upd(2 * v + 1, l, md, i, x);
        else upd(2 * v + 2, md, r, i, x);
        t[v] = max(t[2 * v + 1], t[2 * v + 2]);
    }
    ll get(ll v, ll l, ll r, ll ql, ll qr) {
        if (l >= qr || ql >= r) return 0;
        if (l >= ql && r <= qr) return t[v];
        ll md = (l + r) / 2;
        return max(get(2 * v + 1, l, md, ql, qr), get(2 * v + 2, md, r, ql, qr));
    }
};
void solve() {
    ll n, d;
    cin >> n >> d;
    vector<ll> a(n), sa;
    for (ll& x : a) cin >> x;
    sa = a;
    sort(sa.begin(), sa.end());
    sa.resize(unique(sa.begin(), sa.end()) - sa.begin());
    st d0(n + 1), d1(n + 1), d2(n + 1);
    vector<vector<ll>> dp(n, vector<ll>(2, 1));
    for (ll i = 0; i < n; i++) {
        ll pa = lower_bound(sa.begin(), sa.end(), a[i]) - sa.begin();
        ll pb = lower_bound(sa.begin(), sa.end(), a[i] + d) - sa.begin();
        if (i) {
            dp[i][0] = d0.get(0, 0, n + 1, 0, pa) + 1;
            dp[i][1] = d1.get(0, 0, n + 1, 0, pb) + 1;
            dp[i][1] = max(dp[i][1], d2.get(0, 0, n + 1, 0, pa) + 1);
        } else {
            dp[i][0] = dp[i][1] = 1;
        }
        d0.upd(0, 0, n + 1, pa, max(1ll, dp[i][0]));
        d1.upd(0, 0, n + 1, pa, max(1ll, dp[i][0]));
        d2.upd(0, 0, n + 1, pa, max(1ll, dp[i][1]));
        //cout << dp[i][0] << ' ' << dp[i][1] << '\n';
        for (ll j = 0; j < i; j++) {
            // if (a[i] > a[j]) dp[i][0] = max(dp[i][0], dp[j][0] + 1);
            // if (a[i] + d > a[j]) dp[i][1] = max(dp[i][1], dp[j][0] + 1);
            // if (a[i] > a[j]) dp[i][1] = max(dp[i][1], dp[j][1] + 1);
        }
    }
    ll ans = 0;
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < dp[i].size(); j++) ans = max(ans, dp[i][j]);
    }
    cout << ans;
}
signed main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    ll t = 1;
    //cin >> t;
    while (t--) {
        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...