Submission #717010

#	Time	Username	Problem	Language	Result	Execution time	Memory
717010		AmirAli_H1	Global Warming (CEOI18_glo)	C++17	100 / 100	1030 ms	60256 KiB

glo

// In the name of Allah

#include <bits/stdc++.h>
using namespace std;

typedef long long int	ll;
typedef long double	ld;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;

#define all(x)		(x).begin(),(x).end()
#define len(x)		((ll) (x).size())
#define F		first
#define S		second
#define pb		push_back
#define sep             ' '
#define endl            '\n'
#define Mp		make_pair
#define debug(x)	cerr << #x << ": " <<  x << endl;
#define kill(x)		cout << x << '\n', exit(0);
#define set_dec(x)	cout << fixed << setprecision(x);
#define file_io(x,y)	freopen(x, "r", stdin); freopen(y, "w", stdout);

int n; ll x;
const int maxn = 1e6 + 5;
const ll oo = 1e18;
ll a[maxn]; ll res1[maxn], res2[maxn];
ll ans = 0;
vector<ll> arr;
ll t[4 * maxn]; vector<pll> vc[maxn];

int GI(ll val) {
	return lower_bound(all(arr), val) - arr.begin();
}

void set_val(int v, int tl, int tr, int i, ll x) {
	if (i >= tr || i < tl) return ;
	if (tr - tl == 1) {
		t[v] = x;
		return ;
	}
	int mid = (tl + tr) / 2;
	set_val(2 * v + 1, tl, mid, i, x); set_val(2 * v + 2, mid, tr, i, x);
	t[v] = max(t[2 * v + 1], t[2 * v + 2]);
}

ll get_max(int v, int tl, int tr, int l, int r) {
	l = max(l, tl); r = min(r, tr);
	if (l >= tr || r <= tl) return 0;
	if (l == tl && r == tr) return t[v];
	int mid = (tl + tr) / 2;
	return max(get_max(2 * v + 1, tl, mid, l, r), get_max(2 * v + 2, mid, tr, l, r));
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> n >> x;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		arr.pb(a[i]); arr.pb(a[i] - x + 1); arr.pb(a[i] + x - 1);
	}
	arr.pb(-oo); arr.pb(oo);
	sort(all(arr)); arr.resize(unique(all(arr)) - arr.begin());
	
	// Part 1
	for (int i = 0; i <= n + 1; i++) vc[i].clear();
	fill(t, t + 4 * len(arr), 0);
	
	reverse(a + 1, a + (n + 1));
	for (int i = 1; i <= n; i++) a[i] = -a[i];
	fill(res2, res2 + (n + 2), oo);
	res2[0] = -oo;
	for (int i = 1; i <= n; i++) {
		int j = lower_bound(res2, res2 + (n + 1), a[i]) - res2;
		if (a[i] > res2[j - 1]) {
			res2[j] = a[i];
			int jx = GI(-res2[j]);
			vc[i].pb(Mp(get_max(0, 0, len(arr), jx, jx + 1), -res2[j]));
			set_val(0, 0, len(arr), GI(-res2[j]), j);
		}
	}
	reverse(a + 1, a + (n + 1));
	for (int i = 1; i <= n; i++) a[i] = -a[i];
	
	fill(res1, res1 + (n + 2), oo);
	res1[0] = -oo;
	for (int i = 1; i <= n; i++) {
		int j = lower_bound(res1, res1 + (n + 1), a[i]) - res1;
		if (a[i] > res1[j - 1]) {
			res1[j] = a[i];
			for (auto f : vc[n - i + 1]) {
				set_val(0, 0, len(arr), GI(f.S), f.F);
			}
			int j1 = GI(res1[j] - x + 1), j2 = GI(oo);
			ans = max(ans, j + get_max(0, 0, len(arr), j1, j2));
		}
	}
	
	for (int i = 0; i <= n; i++) {
		if (res1[i] < oo) ans = max(ans, 0ll + i);
	}
	
	// Part 2
	for (int i = 0; i <= n + 1; i++) vc[i].clear();
	fill(t, t + 4 * len(arr), 0);
	
	fill(res1, res1 + (n + 2), oo);
	res1[0] = -oo;
	for (int i = 1; i <= n; i++) {
		int j = lower_bound(res1, res1 + (n + 1), a[i]) - res1;
		if (a[i] > res1[j - 1]) {
			res1[j] = a[i];
			int jx = GI(res1[j]);
			vc[i].pb(Mp(get_max(0, 0, len(arr), jx, jx + 1), res1[j]));
			set_val(0, 0, len(arr), GI(res1[j]), j);
		}
	}
	
	reverse(a + 1, a + (n + 1));
	for (int i = 1; i <= n; i++) a[i] = -a[i];
	fill(res2, res2 + (n + 2), oo);
	res2[0] = -oo;
	for (int i = 1; i <= n; i++) {
		int j = lower_bound(res2, res2 + (n + 1), a[i]) - res2;
		if (a[i] > res2[j - 1]) {
			res2[j] = a[i];
			for (auto f : vc[n - i + 1]) {
				set_val(0, 0, len(arr), GI(f.S), f.F);
			}
			int j1 = GI(-oo) + 1, j2 = GI(-res2[j] + x - 1) + 1;
			ans = max(ans, j + get_max(0, 0, len(arr), j1, j2));
		}
	}
	reverse(a + 1, a + (n + 1));
	for (int i = 1; i <= n; i++) a[i] = -a[i];
	
	for (int i = 0; i <= n; i++) {
		if (res2[i] < oo) ans = max(ans, 0ll + i);
	}
	
	cout << ans << endl;
	
	return 0;
}

• 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