Submission #97732

#	Time	Username	Problem	Language	Result	Execution time	Memory
97732		luciocf	Global Warming (CEOI18_glo)	C++14	28 / 100	2058 ms	12280 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 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)});
}

void clear(node *t)
{
	if (!t) return;

	clear(t->l); clear(t->r);

	delete(t);
}

int main(void)
{
	scanf("%d %d", &n, &x);

	node *t = NULL;

	for (int i = 1; i <= n; i++)
		scanf("%d", &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);
	}

	clear(t);
	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;

	clear(t);
	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);
	}

	clear(t);
	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);
	}

	printf("%d\n", ans);
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:91:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &x);
  ~~~~~^~~~~~~~~~~~~~~~~
glo.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &num[i]);
   ~~~~~^~~~~~~~~~~~~~~

• 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