제출 #515744

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
515744		andrei_boaca	Global Warming (CEOI18_glo)	C++17	100 / 100	126 ms	8104 KiB

glo

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll n,x,v[200005],ans,dp[200005],maxim[200005],minim[200005],pref[200005];
ll getLIS()
{
    ll rez=0;
    for(int i=1;i<=n;i++)
        maxim[i]=-3e9;
    for(int i=n;i>=1;i--)
    {
        int lg=0;
        int st=1;
        int dr=n-i;
        while(st<=dr)
        {
            int mij=(st+dr)/2;
            if(maxim[mij]>v[i])
            {
                lg=mij;
                st=mij+1;
            }
            else
                dr=mij-1;
        }
        dp[i]=lg+1;
        rez=max(rez,dp[i]);
        maxim[dp[i]]=max(maxim[dp[i]],v[i]);
    }
    return rez;
}
void getprefLIS()
{
    ll rez=0;
    for(int i=1;i<=n;i++)
        minim[i]=3e9;
    for(int i=1;i<=n;i++)
    {
        ll lg=0;
        ll st=1;
        ll dr=i-1;
        while(st<=dr)
        {
            ll mij=(st+dr)/2;
            if(minim[mij]<v[i])
            {
                lg=mij;
                st=mij+1;
            }
            else
                dr=mij-1;
        }
        pref[i]=lg+1;
        minim[pref[i]]=min(minim[pref[i]],v[i]);
    }

}
int main()
{
    cin>>n>>x;
    for(int i=1;i<=n;i++)
        cin>>v[i];
    ans=getLIS();
    getprefLIS();
    for(ll i=1;i<=n;i++)
        maxim[i]=-3e9;
    for(int i=n;i>=1;i--)
    {
        ll val=pref[i];
        ll lg=0;
        ll st=1;
        ll dr=n-i;
        while(st<=dr)
        {
            ll mij=(st+dr)/2;
            if(maxim[mij]>v[i]-x)
            {
                lg=mij;
                st=mij+1;
            }
            else
                dr=mij-1;
        }
        ans=max(ans,val+lg);
        maxim[dp[i]]=max(maxim[dp[i]],v[i]);
    }
    cout<<ans;
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

glo.cpp: In function 'void getprefLIS()':
glo.cpp:35:8: warning: unused variable 'rez' [-Wunused-variable]
   35 |     ll rez=0;
      |        ^~~

• 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