제출 #1218042

#제출 시각아이디문제언어결과실행 시간메모리
1218042johuthaGlobal Warming (CEOI18_glo)C++20
100 / 100
102 ms11388 KiB
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

#define ll long long

using namespace std;

vector<ll> lis(int n, vector<ll> arr)
{
    vector<ll> ends_at(n + 1, 1e18);
    ends_at[0] = -1e18;

    vector<ll> inds;

    for (auto v : arr)
    {
        ll ind = lower_bound(ends_at.begin(), ends_at.end(), v) - ends_at.begin();
        ends_at[ind] = v;
        inds.push_back(ind);
    }
    return inds;
}

signed main()
{
    int n;
    ll x;
    cin >> n >> x;

    vector<ll> ip(n);
    for (int i = 0; i < n; i++) cin >> ip[i];

    auto lis_left = lis(n, ip);

    reverse(ip.begin(), ip.end());
    for (int i = 0; i < n; i++) ip[i] = -ip[i];
    auto lis_right = lis(n, ip);
    reverse(lis_right.begin(), lis_right.end());

    reverse(ip.begin(), ip.end());
    for (int i = 0; i < n; i++) ip[i] = -ip[i];

    set<pair<ll,ll>> active;
    active.insert({1e18, 0});

    ll ans = 0;

    for (int i = n - 1; i >= 0; i--)
    {
        pair<ll, ll> query = {ip[i] - x + 1, -1};
        ll candidate = lis_left[i] + active.lower_bound(query)->second;
        ans = max(ans, candidate);

        pair<ll, ll> curr = {ip[i], lis_right[i]};
        auto [it, _] = active.insert(curr);
        while (it != active.begin() && prev(it)->second <= curr.second) active.erase(prev(it));
    }

    cout << ans << "\n";
}
#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...