Submission #636303

#	Time	Username	Problem	Language	Result	Execution time	Memory
636303		Zian_Jacobson	Global Warming (CEOI18_glo)	C++17	17 / 100	54 ms	8156 KiB

glo

#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());
	}
	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 = lower_bound(suf_lis.begin(), suf_lis.end(), t[i - 1] + 1 - x, greater<ll>());
		if (it1 == suf_lis.end()) it1--;
		suf[i - 1] = it1 - suf_lis.begin();
	}
	ll ans = 0;
	for (int i = 1; i <= n; i++) ans = max(ans, pref[i] + suf[i]);
	cout << ans << "\n";
	return 0;
}

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