Submission #1218042

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218042		johutha	Global Warming (CEOI18_glo)	C++20	100 / 100	102 ms	11388 KiB

glo

#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";
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 25 / 25