| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1220537 | TsotneSV | Global Warming (CEOI18_glo) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
/*⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⠀⠀⠀⠀⠀⠀⠀⡄⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⣿⠛⣿⠀⠀⠀⠀⣤⣿⢻⡇⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⣿⡛⠀⣤⣿⣿⣤⣤⣿⣿⣤⢸⡇⠀
⠀⠀⠀⠀⠀⠀⠀⠀⣴⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠀
⠀⠀⠀⠀⠀⠀⠀⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡗⠀
⢠⣼⣿⣿⣿⣿⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷
⢸⣿⣿⡟⠛⠛⢿⣿⣿⣿⣿⣿⣿⣿⣤⣤⣤⣿⣿⣿⣿⣤⣤⣼⣿⣿
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠛⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⠋
*/
#define fi first
#define se second
#define pb push_back
#define ins insert
#define sz(a) (int)(a.size())
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
//#define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
#include "debug.h"
#else
#define debug(...)
#endif
//const int mod = 1e9+7;
//const int mod = 998244353;
const int MAXN=2e5+5;
const ll inf=2e9,INF=1e18;
int n,d,t[MAXN],l[MAXN];
void solve(int tc = 0){
cin>>n>>d; int ans = 1; vi dp(n+1,inf),dpR(n+1,inf); dp[0] = -inf; dpR[0] = -inf;
for(int i=1;i<=n;i++) {
cin>>t[i];
int lis = (--lower_bound(all(dp),t[i])) - dp.begin();
dp[lis+1] = min(dp[lis+1],t[i]); l[i] = lis + 1;
}
for(int i=n;i>0;i--) {
if(dp[i] != inf) ans = max(ans,i);
int R = (--lower_bound(all(dpR),-(t[i]-d))) - dpR.begin();
ans = max(ans,l[i] + R);
int lis = (--lower_bound(all(dpR),-t[i])) - dpR.begin();
dpR[lis+1] = min(dpR[lis+1],-t[i]);
}
print(ans);
}
signed main(){
ios_base::sync_with_stdio(false); cin.tie(0);
int tc=1;
//cin>>tc;
for(int t = 0; t < tc; t++) solve(t);
}