Submission #594058

#	Time	Username	Problem	Language	Result	Execution time	Memory
594058		penguinhacker	Global Warming (CEOI18_glo)	C++17	100 / 100	359 ms	18892 KiB

glo

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

#define ll long long
#define ar array

const int mxN=2e5;
int n, x, a[mxN], ans;
vector<int> d, changes[mxN];

struct st {
	int st[1<<19];
	void upd(int i, int x, int u=1, int l=0, int r=d.size()-1) {
		if (l==r) {
			st[u]=x;
			return;
		}
		int mid=(l+r)/2;
		i<=mid?upd(i, x, 2*u, l, mid):upd(i, x, 2*u+1, mid+1, r);
		st[u]=max(st[2*u], st[2*u+1]);
	}
	int qry(int ql, int qr, int u=1, int l=0, int r=d.size()-1) {
		if (l>qr||r<ql) return 0;
		if (ql<=l&&r<=qr) return st[u];
		int mid=(l+r)/2;
		return max(qry(ql, qr, 2*u, l, mid), qry(ql, qr, 2*u+1, mid+1, r));
	}
} lhs, rhs;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> x;
	for (int i=0; i<n; ++i)
		cin >> a[i];
	d=vector<int>(a, a+n);
	sort(d.begin(), d.end());
	d.resize(unique(d.begin(), d.end())-d.begin());
	for (int i=0; i<n; ++i) {
		a[i]=lower_bound(d.begin(), d.end(), a[i])-d.begin();
		int dp=lhs.qry(0, a[i]-1)+1;
		ans=max(ans, dp);
		lhs.upd(a[i], dp);
		changes[a[i]].push_back(dp);
	}
	for (int i=n-1; ~i; --i) {
		changes[a[i]].pop_back();
		lhs.upd(a[i], changes[a[i]].size()?changes[a[i]].back():0);
		int dp=rhs.qry(a[i]+1, d.size()-1)+1;
		rhs.upd(a[i], dp);
		int pos=lower_bound(d.begin(), d.end(), d[a[i]]+x)-d.begin();
		//if (i==4)
		//	cout << dp << " " << d[a[i]]+x << " " << d[pos] << endl;
		//cout << lhs.qry(0, pos-1) << " " << dp << endl;
		ans=max(ans, lhs.qry(0, pos-1)+dp);
	}
	cout << ans;
	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