| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 920153 | Muhammad_Aneeq | Global Warming (CEOI18_glo) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*
بسم الله الرحمن الرحيم
Author:
(:Muhammad Aneeq:)
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define int long long
int const N=2e5+10;
int a[N]={};
int n;
inline void solve()
{
int x;
cin>>n>>x;
for (int i=0;i<n;i++)
cin>>a[i];
int ans=0;
vector<int>dp;
pair<int,int> pre[n+1]={};
pre[0]={0,-1e9-10};
int maxval[2][n+10]={};
for (int i=0;i<n+10;i++)
maxval[0][i]=maxval[1][i]=-1e9-10;
maxval[0][0]=-1e9-10;
for (int i=0;i<n;i++)
{
int z=lower_bound(begin(dp),end(dp),a[i])-begin(dp);
if (z==dp.size())
dp.push_back(a[i]);
else
dp[z]=a[i];
z++;
if (maxval[0][z]==-1e9-10)
maxval[0][z]=max(maxval[0][z],a[i]);
pre[i+1]={dp.size(),dp.back()};
}
for (int i=0;i<n;i++)
a[i]=-a[i];
reverse(a,a+n);
dp={};
pair<int,int>suf[n+1]={};
suf[0]={0,-1e9-10};
for (int i=0;i<n;i++)
{
int z=lower_bound(begin(dp),end(dp),a[i])-begin(dp);
if (z==dp.size())
dp.push_back(a[i]);
else
dp[z]=a[i];
z++;
if (maxval[1][z]==-1e9-10)
maxval[1][z]=max(maxval[1][z],-a[i]);
suf[i+1]={dp.size(),-dp.back()};
}
for (int i=0;i<=n;i++)
{
if (maxval[0][pre[i].first]-maxval[1][suf[n-i].first]<x)
ans=max(ans,pre[i].first+suf[n-i].first);
}
cout<<ans<<endl;
}
signed main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
solve();
}