Submission #1038595

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038595		vjudge1	Global Warming (CEOI18_glo)	C++14	100 / 100	226 ms	7628 KiB

glo

#include <bits/stdc++.h>

using namespace std;

int n, x;

int a[200005];

int o[200005];

int st[200005 * 4];

void upd(int i, int v) {
	
	int l = 1, r = n, id = 1;
	
	while (l < r) {
		int mid = (l + r) / 2;
		id *= 2;
		
		if (i <= mid) {
			r = mid;
		} else {
			l = mid + 1;
			id++;
		}
		
	}
	
	st[id] = max(st[id], v);
	
	while (id > 1) {
		
		id /= 2;
		st[id] = max(st[id * 2], st[id * 2 + 1]);
		
	}
}

int get(int i, int j, int id = 1, int l = 1, int r = n) {
	
	if (i > j) {
		return 0;
	}
	
	if (i <= l && r <= j) {
		return st[id];
	}
	
	int mid = (l + r) / 2;
	
	if (i <= mid && mid < j) {
		return max(get(i, j, id * 2, l, mid), get(i, j, id * 2 + 1, mid + 1, r));
	}
	
	if (mid < i) {
		return get(i, j, id * 2 + 1, mid + 1, r);
	}
	
	return get(i, j, id * 2, l, mid);
}

int lis_l[200005], lis_r[200005];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> x;
	
	vector<int> val;
	
	for (int i = 1; i <= n; ++i) {
		
		cin >> a[i];
		
		val.emplace_back(a[i]);
	}
	
	sort(val.begin(), val.end());
	
	val.erase(unique(val.begin(), val.end()), val.end());
	
	for (int i = 1; i <= n; ++i) {
		
		o[i] = lower_bound(val.begin(), val.end(), a[i]) - val.begin() + 1;
		
	}
	
	memset(st, 0, sizeof st);
	
	for (int i = 1; i <= n; ++i) {
		
		lis_l[i] = get(1, o[i] - 1) + 1;
		
		upd(o[i], lis_l[i]);
	}
	
	memset(st, 0, sizeof st);
	
	for (int i = n; i >= 1; --i) {
		
		lis_r[i] = get(o[i] + 1, n) + 1;
		
		upd(o[i], lis_r[i]);
	}
	
	memset(st, 0, sizeof st);

	int ans = 0;
	
	for (int i = 1; i <= n; ++i) {
		
		int j = upper_bound(val.begin(), val.end(), a[i] + x - 1) - val.begin();
		
		ans = max(ans, get(1, j) + lis_r[i]);
		
		upd(o[i], lis_l[i]);
	}
	
	cout << ans << '\n';
}

• 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