Submission #636309

#TimeUsernameProblemLanguageResultExecution timeMemory
636309Zian_JacobsonGlobal Warming (CEOI18_glo)C++17
100 / 100
57 ms8624 KiB
#include<bits/stdc++.h>
using namespace std;
#define cIO ios_base::sync_with_stdio(0);cin.tie(0)
#define fileIO(x) ifstream fin(string(x)+".in"); ofstream fout(string(x)+".out")
#define cont(container, object) (container.find(object)!=container.end())
#define sz(x) (int) (x).size()
#define ll long long
#define v vector
const ll MX = 200005, INF=LLONG_MAX/2, NEG_INF=LLONG_MIN/2;
ll n, x, t[MX];
ll suf[MX];//[i]: for the suffix [i+1..n], the maximum increasing subsequence such that we can still add t[i]-x to the beginning of it
ll pref[MX];//[i]: LIS that includes t[i] in the prefix ending at i;
int main()
{
	cIO;
	cin >> n >> x;
	for (int i = 1; i <= n; i++) cin >> t[i];
	v<ll> pref_lis = {NEG_INF};
	for (int i = 1; i <= n; i++)
	{
		auto it = upper_bound(pref_lis.begin(), pref_lis.end(), t[i] - 1);
		if (it != pref_lis.end())//exists
			*it = t[i];
		else pref_lis.push_back(t[i]);
		pref[i] = (lower_bound(pref_lis.begin(), pref_lis.end(), t[i]) - pref_lis.begin());//find the value
	}
	v<ll> suf_lis = { INF };
	suf[n] = 0;
	for (int i = n; i >= 2; i--)//we don't want to go to the start since that will cause overflow
	{
		auto it = upper_bound(suf_lis.begin(), suf_lis.end(), t[i] + 1, greater<ll>());
		if (it != suf_lis.end())
			*it = t[i];
		else suf_lis.push_back(t[i]);
		auto it1 = upper_bound(suf_lis.begin(), suf_lis.end(), t[i - 1] + 1 - x, greater<ll>());
		suf[i - 1] = it1 - suf_lis.begin()-1;
	}
	ll ans = 0;
	for (int i = 1; i <= n; i++) ans = max(ans, pref[i] + suf[i]);
	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...