oj.uz

답안 #97730

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
97730 2019-02-17T20:25:56 Z luciocf Global Warming (CEOI18_glo) C++14
5 / 100
 1124 ms 40296 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5+10;
const int inf = 1e9+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->m;
}

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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 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 428 KB Output is correct
11 Correct 3 ms 384 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 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 428 KB Output is correct
11 Correct 3 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 Incorrect 2 ms 384 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 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 428 KB Output is correct
11 Correct 3 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 Incorrect 2 ms 384 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1124 ms 40296 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 171 ms 10468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 407 ms 20284 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 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 428 KB Output is correct
11 Correct 3 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 Incorrect 2 ms 384 KB Output isn't correct
15 Halted 0 ms 0 KB -