Submission #570136

#	Time	Username	Problem	Language	Result	Execution time	Memory
570136		MarcosPauloEvers	Global Warming (CEOI18_glo)	C++17	100 / 100	53 ms	4312 KiB

glo

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5 + 10;
int n, x;
int arr[MAXN], sz[MAXN];
vector<int> lis;

int
main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> x;

	for(int i = 0; i < n; i++)
		cin >> arr[i];

	for(int i = n - 1; i >= 0; i--)
	{
		int l = 0, r = lis.size() - 1;
		while(l <= r)
		{
			int t = (l + r) >> 1;

			if(lis[t] > arr[i]) l = t + 1;
			else r = t - 1;
		}
	
		if(l == lis.size()) lis.push_back(arr[i]), sz[i] = lis.size();
		else lis[l] = arr[i], sz[i] = l + 1;
	}
	lis.clear();
	int ans = 0;
	for(int i = 0; i < n; i++)
	{
		ans = max(ans, sz[i] + int(lower_bound(begin(lis), end(lis), arr[i] + x) - begin(lis)));
	
		auto it = lower_bound(begin(lis), end(lis), arr[i]);

		if(it == end(lis)) lis.push_back(arr[i]);
		else *it = arr[i];
	}

	cout << ans << "\n";
	return 0;
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:30:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   if(l == lis.size()) lis.push_back(arr[i]), sz[i] = lis.size();
      |      ~~^~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 25 / 25