Submission #774317

#	Time	Username	Problem	Language	Result	Execution time	Memory
774317		parsadox2	Cloud Computing (CEOI18_clo)	C++14	0 / 100	1 ms	1108 KiB

clo

#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());

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;
}

• Subtask 1: 0 / 18
• Subtask 2: 0 / 18
• Subtask 3: 0 / 18
• Subtask 4: 0 / 18
• Subtask 5: 0 / 18
• Subtask 6: 0 / 10