Submission #97731

#	Time	Username	Problem	Language	Result	Execution time	Memory
97731		luciocf	Global Warming (CEOI18_glo)	C++14	28 / 100	2061 ms	42360 KiB

glo

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5+10;

struct node
{
	int v, m, maior, w, sz;
	node *l, *r;

	node(int vv, int mm)
	{
		v = vv, maior = m = mm, sz = 1, w = rand();
		l = r = NULL;
	}
};

typedef node*& node_t;

int n, x;
int num[maxn];
int pref[maxn], suf[maxn];

int sz(node *t)
{
	if (!t) return 0;
	return t->sz;
}

int maior(node *t)
{
	if (!t) return 0;
	return t->maior;
}

void op(node *t)
{
	if (t)
	{
		t->sz = sz(t->l)+sz(t->r)+1;
		t->maior = max({maior(t->l), maior(t->r), t->m});
	}
}

void split(node *t, int x, node_t l, node_t r)
{
	if (!t) l = r = NULL;
	else if (t->v > x) split(t->l, x, l, t->l), r = t;
	else split(t->r, x, t->r, r), l = t;

	op(t);
}

void merge(node_t t, node *l, node *r)
{
	if (!l || !r) t = (l ? l : r);
	else if (l->w > r->w) merge(l->r, l->r, r), t = l;
	else merge(r->l, l, r->l), t = r;

	op(t);
}

void insert(node_t t, node *it)
{
	if (!t) t = it;
	else if (it->w > t->w) split(t, it->v, it->l, it->r), t = it;
	else insert((it->v > t->v ? t->r : t->l), it);

	op(t);
}

int get_menor(node *t, int v)
{
	if (!t) return 0;

	if (t->v >= v) return get_menor(t->l, v);
	return max({t->m, maior(t->l), get_menor(t->r, v)});
}

int get_maior(node *t, int v)
{
	if (!t) return 0;

	if (t->v <= v) return get_maior(t->r, v);
	return max({t->m, maior(t->r), get_maior(t->l, v)});
}

int main(void)
{
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> n >> x;

	node *t = NULL;

	for (int i = 1; i <= n; i++)
		cin >> num[i];

	for (int i = 1; i <= n; i++)
	{
		int val = get_menor(t, num[i]);

		pref[i] = val+1;

		node *aux = new node(num[i], pref[i]);
		insert(t, aux);
	}

	t = NULL;

	for (int i = n; i >= 1; i--)
	{
		int val = get_maior(t, num[i]);

		suf[i] = val+1;

		node *aux = new node(num[i], suf[i]);
		insert(t, aux);
	}

	int ans = 0;
	t = NULL;

	for (int i = 1; i <= n; i++)
	{
		int val = get_menor(t, num[i]+x);

		ans = max(ans, suf[i]+val);

		node *aux = new node(num[i], pref[i]);
		insert(t, aux);
	}

	t = NULL;

	for (int i = n; i >= 1; i--)
	{
		int val = get_maior(t, num[i]-x);

		ans = max(ans, pref[i]+val);

		node *aux = new node(num[i], suf[i]);
		insert(t, aux);
	}

	cout << ans << "\n";
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25