Submission #1045152

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045152		IdanRosen	Global Warming (CEOI18_glo)	C++98	100 / 100	43 ms	8644 KiB

glo

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    ll n, x;
    cin >> n >> x;

    vector<ll> arr(n);
    for (auto &i: arr) cin >> i;

    vector<ll> lis(n);
    {
        vector<ll> dp(n, -1);
        ll len = 0;

        for (ll i = 0; i < n; i++) {
            ll val = arr[i];

            ll start = 0;
            ll end = len;
            while (start < end) {
                ll mid = start + (end - start) / 2;

                if (arr[dp[mid]] < val) start = mid + 1;
                else end = mid;
            }

            lis[i] = start + 1;

            dp[start] = i;
            if (start == len) ++len;
        }
    }

    vector<ll> lis_rev(n);
    {
        vector<ll> dp(n);
        ll len = 0;

        for (ll i = n - 1; i > 0; i--) {
            ll val = arr[i];

            ll start = 0;
            ll end = len;

            while (start < end) {
                ll mid = start + (end - start) / 2;

                if (arr[dp[mid]] > val - x) start = mid + 1;
                else end = mid;
            }

            lis_rev[i] = start + 1;

            start = 0;
            end = len;

            while (start < end) {
                ll mid = start + (end - start) / 2;

                if (arr[dp[mid]] > val) start = mid + 1;
                else end = mid;
            }

            dp[start] = i;
            if (start == len) ++len;
        }
    }

    ll best_lis = 0;
    for (ll i = 0; i < n; i++) best_lis = max(best_lis, lis[i] + lis_rev[i] - 1);

    cout << best_lis;
}

• 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