oj.uz

Submission #97732

# Submission time Handle Problem Language Result Execution time Memory
97732 2019-02-17T20:34:36 Z luciocf Global Warming (CEOI18_glo) C++14
28 / 100
 2000 ms 12280 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 256 KB Output is correct
18 Correct 2 ms 384 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 256 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 4 ms 384 KB Output is correct
21 Correct 4 ms 384 KB Output is correct
22 Correct 4 ms 384 KB Output is correct
23 Correct 4 ms 384 KB Output is correct
24 Correct 4 ms 384 KB Output is correct
25 Correct 3 ms 384 KB Output is correct
26 Correct 3 ms 384 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1261 ms 12124 KB Output is correct
2 Correct 1281 ms 12132 KB Output is correct
3 Correct 1249 ms 12280 KB Output is correct
4 Correct 1261 ms 12144 KB Output is correct
5 Execution timed out 2056 ms 3320 KB Time limit exceeded

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 3216 KB Output is correct
2 Correct 166 ms 3284 KB Output is correct
3 Correct 174 ms 3308 KB Output is correct
4 Execution timed out 2054 ms 2680 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 440 ms 6360 KB Output is correct
2 Correct 464 ms 6244 KB Output is correct
3 Correct 1295 ms 12024 KB Output is correct
4 Execution timed out 2058 ms 3192 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 256 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 4 ms 384 KB Output is correct
21 Correct 4 ms 384 KB Output is correct
22 Correct 4 ms 384 KB Output is correct
23 Correct 4 ms 384 KB Output is correct
24 Correct 4 ms 384 KB Output is correct
25 Correct 3 ms 384 KB Output is correct
26 Correct 3 ms 384 KB Output is correct
27 Correct 1261 ms 12124 KB Output is correct
28 Correct 1281 ms 12132 KB Output is correct
29 Correct 1249 ms 12280 KB Output is correct
30 Correct 1261 ms 12144 KB Output is correct
31 Execution timed out 2056 ms 3320 KB Time limit exceeded