Submission #517295

#	Time	Username	Problem	Language	Result	Execution time	Memory
517295		danikoynov	Global Warming (CEOI18_glo)	C++14	0 / 100	147 ms	4560 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 int maxn = 2e5 + 10;
int n, x, a[maxn], dp[maxn], fp[maxn];
pair < int, int > upd[maxn];
void solve()
{
    cin >> n >> x;
    for (int i = 1; i <= n; i ++)
        cin >> a[i];

    int to = 0;
    dp[0] = -2e9 - 1;
    for (int i = 1; i <= n; i ++)
    {
        int l = 0, r = to;
        while(l <= r)
        {
            int 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;
    }


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

    for (int i = n; i > 0; i --)
    {
        int l = 0, r = ho;
        while(l <= r)
        {
            int 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;

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


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

    cout << ans << endl;

}

int main()
{
    solve();
    return 0;
}

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