Submission #517298

#	Time	Username	Problem	Language	Result	Execution time	Memory
517298		danikoynov	Global Warming (CEOI18_glo)	C++14	100 / 100	103 ms	6860 KiB

glo

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
const ll maxn = 2e5 + 10;
ll n, x, a[maxn], dp[maxn], fp[maxn];
pair < ll, ll > upd[maxn];
void solve()
{
    cin >> n >> x;
    for (ll i = 1; i <= n; i ++)
        cin >> a[i];

    ll to = 0;
    dp[0] = -2e9 - 1;
    for (ll i = 1; i <= n; i ++)
    {
        ll l = 0, r = to;
        while(l <= r)
        {
            ll m = (l + r) / 2;
            if (dp[m] < a[i])
                l = m + 1;
            else
                r = m - 1;
        }
        upd[i] = {l, dp[l]};
        dp[l] = a[i];

        if (l > to)
            to = l, upd[i].second = 2e9 + 1;
    }


    ll ans = to;
    fp[0] = 2e9 + 1;
    ll ho = 0;

    for (ll i = n; i > 0; i --)
    {
        ll l = 0, r = ho;
        while(l <= r)
        {
            ll m = (l + r) / 2;
            if (fp[m] > a[i])
                l = m + 1;
            else
                r = m - 1;
        }
        fp[l] = a[i];
        if (l > ho)
            ho = l;

        dp[upd[i].first] = upd[i].second;

        ll lf = 0, rf = to;
        while(lf <= rf)
        {
            ll mf = (lf + rf) / 2;
            if (dp[mf] - x < a[i])
                lf = mf + 1;
        else
            rf = mf - 1;
        }


        if (rf + l > ans)
            ans = rf + l;
    }

    cout << ans << endl;

}

int main()
{
    solve();
    return 0;
}
/**
10 10
1 1 1 1 1 1 2 2 2 1

*/

• 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