제출 #774318

#제출 시각아이디문제언어결과실행 시간메모리
774318parsadox2Global Warming (CEOI18_glo)C++14
100 / 100
52 ms6964 KiB
#include <bits/stdc++.h>
#define pb 		push_back
#define F		first
#define S 		second
#define debug(x)    cout << #x << "= " << x << ", "
#define ll 		long long
#define fast 		ios::sync_with_stdio(false), cin.tie(0),  cout.tie(0)
#define SZ(x)         (int) x.size()
#define wall 		cout << endl;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define int long long 
const int maxn = 2e5 + 10 , inf = 2e9 + 10;
int n , ar[maxn] , x , lis[maxn] , lds[maxn];

int32_t main()
{
	fast;
	cin >> n >> x;
	for(int i = 0 ; i < n ; i++)  cin >> ar[i];
	lis[0] = inf;
	for(int i = 1 ; i < maxn ; i++)  lis[i] = -inf;
	for(int i = n - 1 ; i > -1 ; i--)
	{
		int low = 0 , high = maxn;
		while(high - low > 1)
		{
			int mid = (high + low) >> 1;
			if(lis[mid] <= ar[i])
				high = mid;
			else 
				low = mid;
		}
		lis[high] = ar[i];
		lds[i] = high;
	}
	int ans = 0;
	for(int i = 0 ; i <= n ; i++)  if(lis[i] != -inf)  ans = i;
	lis[0] = -inf;
	for(int i = 1 ; i < maxn ; i++)  lis[i] = inf;
	for(int i = 0 ; i < n - 1 ; i++)
	{
		int low = 0 , high = maxn;
		while(high - low > 1)
		{
			int mid = (high + low) >> 1;
			if(lis[mid] < ar[i])  low = mid;
			else high = mid;
		}
		lis[high] = ar[i];
		int tmp = ar[i + 1] + x;
		low = 0;   high = maxn;
		while(high - low > 1)
		{
			int mid = (high + low) >> 1;
			if(lis[mid] < tmp)  low = mid;
			else  high = mid;
		}
		ans = max(ans , low + lds[i + 1]);
	}
	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...