Submission #667182

#	Time	Username	Problem	Language	Result	Execution time	Memory
667182		Kahou	Global Warming (CEOI18_glo)	C++14	100 / 100	112 ms	6616 KiB

glo

#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll,ll> pll;

const int N = 2e5 + 50;
int n, m, s[N], f[N];
int x, t[N];
vector<int> dp;
int a[N];
int fen[N];

int get(int i) {
	int out = fen[0];
	for (; i > 0; i -= i&(-i)) {
		out = max(out, fen[i]);
	}
	return out;
}
void upd(int i, int x) {
	if (!i) fen[i] = max(fen[i], x);
	else for (; i <= n; i += i&(-i)) {
		fen[i] = max(fen[i], x);
	}
}


void solve() {
	cin >> n >> x;
	for (int i = 1; i <= n; i++) {
		cin >> t[i];
		a[i] = t[i];
	}
	sort(a+1, a+n+1);
	m = unique(a+1, a+n+1)-a-1;
	for (int i = 1; i <= n; i++) {
		int lb = lower_bound(dp.begin(), dp.end(), t[i])-dp.begin();
		if (lb >= (int)dp.size()) dp.push_back(t[i]);
		dp[lb] = t[i];
		f[i] = lb+1;
	}
	for (int i = 1; i <= n; i++) {
		t[i] = -t[i];
	}
	dp.clear();
	for (int i = n; i >= 1; i--) {
		int lb = lower_bound(dp.begin(), dp.end(), t[i])-dp.begin();
		if (lb >= (int)dp.size()) dp.push_back(t[i]);
		dp[lb] = t[i];
		s[i] = lb+1;
	}
	for (int i = 1; i <= n; i++) {
		t[i] = -t[i];
	}
	
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		int id = lower_bound(a+1, a+m+1, t[i]+x)-a-1;
		ans = max(ans, s[i] + get(id));
		int id2 = lower_bound(a+1, a+m+1, t[i])-a;
		upd(id2, f[i]);
	}
	cout << ans << endl;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	solve();
	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