Submission #1164167

#TimeUsernameProblemLanguageResultExecution timeMemory
1164167alir3za_zar3Global Warming (CEOI18_glo)C++20
100 / 100
28 ms5824 KiB
// 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';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...