Submission #1164167

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164167		alir3za_zar3	Global Warming (CEOI18_glo)	C++20	100 / 100	28 ms	5824 KiB

glo

// Alir3za.Zar3 -> Shiraz , Iran
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define     int     long long

const int mxN = 2e5+7;
int n,x,out , v[mxN],dp[mxN];
vector<int> px , sx;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);     cout.tie(0);
        
    cin >> n >> x;
    for (int i=1; i<=n; i++)
        cin >> v[i];
    for (int i=1; i<=n; i++)
    {
        int sz = px.size();
        auto id = lower_bound(px.begin(),px.end(),v[i])-px.begin();
        dp[i] = id+1;
        if (id < sz) px[id] = v[i];
        else px.push_back(v[i]);
    }
    out = px.size();
    for (int i=n; i; i--)
    {
        int sz = sx.size();
        int l=-1 , r=sx.size();
        while (r-l > 1)
        {
            int o = l+r>>1;
            if (sx[o] > v[i]-x) l=o;
            else r=o;
        }
        out = max(out , dp[i]+l+1);

        l=0 , r=sx.size();
        while (r-l > 1)
        {
            int o = l+r>>1;
            if (sx[o] >= v[i]) l=o;
            else r=o;
        }
        if (l<sz and sx[l] > v[i]) l++;
        if (l == sz) sx.push_back(v[i]);
        else sx[l] = v[i];
    }
    cout << out << '\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