제출 #1348681

#제출 시각아이디문제언어결과실행 시간메모리
1348681kantaponzGlobal Warming (CEOI18_glo)C++20
100 / 100
61 ms6604 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int nx = 2e5 + 5;

int n;
ll x, t[nx];
int mp[nx];
vector<int> tmp;
int tree[nx];
int dp[nx];

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

int query(int idx) {
    int ans = 0;
    for (int i = idx; i < nx; i += (i & -i)) {
        ans = max(ans, tree[i]);
    }
    return ans;
}


int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> n >> x;
    for (int i = 1; i <= n; i++) cin >> t[i], tmp.push_back(t[i]);
    sort(tmp.begin(),tmp.end());
    tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
    for (int i = 1; i <= n; i++) {
        mp[i] = lower_bound(tmp.begin(), tmp.end(), t[i]) - tmp.begin() + 1;
    }

    for (int i = n; i >= 1; i--) {
        dp[i] = query(mp[i] + 1) + 1;
        update(mp[i], dp[i]);
    }

    //for (int i = 1; i <= n; i++) cout << dp[i] << " ";
    //cout << endl;

    int ans = 0;
    vector<ll> v;
    for (int i = 1; i <= n; i++) {
        int it1 = lower_bound(v.begin(), v.end(), t[i] + x) - v.begin() - 1;
        ans = max(ans, dp[i] + max(0, it1 + 1));
        auto idx = lower_bound(v.begin(),v.end(),t[i]);
        if (idx == v.end()) v.push_back(t[i]);
        else *idx = t[i];
        //cout << dp[i] + max(0, it1) << " ";
    }

    cout << ans;
}

/*
8 10
7 3 5 12 2 7 3 4

5
*/
#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...