제출 #77951

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
77951		aminra	Global Warming (CEOI18_glo)	C++14	100 / 100	706 ms	32640 KiB

glo

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MOD = (int)1e9 + 7;
const int MAXN = (int)2e5 + 7;
const int infint = (int)1e9;
const ll inf = (ll)1e18;
int seg1[4 * MAXN], seg2[4 * MAXN], x, n, a[MAXN];
unordered_map<int, int> hsh, rev;
void add(int node, int st, int en, int idx, int val, bool c)
{
	if(en - st < 2)
	{
		if(c)
			seg1[node] = max(seg1[node], val);
		else
			seg2[node] = max(seg2[node], val);
		return;
	}
	int mid = (st + en) >> 1;
	if(idx < mid)
		add(node << 1, st, mid, idx, val, c);
	else
		add(node << 1 | 1, mid, en, idx, val, c);
	seg1[node] = max(seg1[node << 1], seg1[node << 1 | 1]);
	seg2[node] = max(seg2[node << 1], seg2[node << 1 | 1]);
}
int get(int node, int st, int en, int l, int r, int c)
{
	if(st >= r || l >= en)
		return 0;
	if(l <= st && en <= r)
	{
		if(c)
			return seg1[node];
		else
			return seg2[node];
	}
	int mid = (st + en) >> 1;
	return max(get(node << 1, st, mid, l, r, c), get(node << 1 | 1, mid, en, l, r, c));
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> x;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	set<int> S;
	for (int i = 0; i < n; i++)
		S.insert(a[i]);
	int cnt = 0;
	vector<int> v;
	for (auto u : S)
		v.push_back(u), hsh[u] = cnt, rev[cnt++] = u;
	add(1, 0, n, hsh[a[0]], 1, 0);
	add(1, 0, n, hsh[a[0]], 1, 1);
	for (int i = 1; i < n; i++)
	{
		int t = upper_bound(v.begin(), v.end(), a[i] + x - 1) - v.begin();
		int p = get(1, 0, n, 0, t, 1);
		if(hsh[a[i]] != 0)
			 p = max(p, get(1, 0, n, 0, hsh[a[i]], 0));
		add(1, 0, n, hsh[a[i]], p + 1, 0);	
		//--------------
		if(hsh[a[i]] == 0)
			p = 0;
		else
			p = get(1, 0, n, 0, hsh[a[i]], 1);
		add(1, 0, n, hsh[a[i]], p + 1, 1);
	}
	cout << get(1, 0, n, 0, n, 0) << "\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