제출 #768897

#제출 시각아이디문제언어결과실행 시간메모리
7688971neGlobal Warming (CEOI18_glo)C++14
100 / 100
57 ms14800 KiB
/*
*  author : Apiram                  
*  created: 29.06.2023 01:29:41
*/

#include<bits/stdc++.h>
using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n,x;cin>>n>>x;
	vector<long long>arr(n);
	for (int i = 0;i<n;++i){
		cin>>arr[i];
	}
	const long long inf = 1e12;
	int ans = 0;
	vector<vector<long long>>dp(n + 1,vector<long long>(2,inf));
	for (int i = 0;i<n;++i){
		int left = 0,right = i - 1;
		int pos = -1;
		while(left<=right){
			int mid = (left + right)>>1;
			if (dp[mid][0] < arr[i] + x){
				//cout<<dp[mid][0]<<" "<<"check"<<" "<<mid<<'\n';
				pos = mid;
				left = mid + 1;
			}
			else if (dp[mid][1] < arr[i]){
				pos = mid;
				left = mid + 1;
			}
			else right = mid - 1;
		}
		ans = max(pos + 2,ans);
		dp[pos + 1][1] = min(dp[pos + 1][1],arr[i]);
		//cout<<pos<<'\n';
		left = 0,right = i - 1;
		pos = -1;	
		while(left<=right){
			int mid = (left + right)>>1;
			if (dp[mid][0] < arr[i]){
				pos = mid;
				left = mid + 1;
			}	
			else right = mid - 1;
		}
		dp[pos + 1][0] = min(arr[i],dp[pos + 1][0]);
		ans = max(ans,pos + 2);		
		//cout<<pos<<'\n';
	}
	cout<<ans<<'\n';
	return 0;
}
#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...