Codeforces Round #271 (Div. 2)——E. Pillars

E. Pillars
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Marmot found a row with n pillars. The i-th pillar has the height of hi meters. Starting from one pillar i1, Marmot wants to jump on the pillars i2, ..., ik. (1 ≤ i1 < i2 < ... < ik ≤ n). From a pillar i Marmot can jump on a pillar j only if i < j and |hi - hj| ≥ d, where |x| is the absolute value of the number x.
Now Marmot is asking you find out a jump sequence with maximal length and print it.
Input
The first line contains two integers n and d (1 ≤ n ≤ 105, 0 ≤ d ≤ 109).
The second line contains n numbers h1, h2, ..., hn (1 ≤ hi ≤ 1015).
Output
The first line should contain one integer k, the maximal length of a jump sequence.
The second line should contain k integers i1, i2, ..., ik (1 ≤ i1 < i2 < ... < ik ≤ n), representing the pillars' indices from the maximal length jump sequence.
If there is more than one maximal length jump sequence, print any.
Sample test(s)
Input

5 2
1 3 6 7 4

Output

4
1 2 3 5 

Input

10 3
2 1 3 6 9 11 7 3 20 18

Output

6
1 4 6 7 8 9 

Note
In the first example Marmot chooses the pillars 1, 2, 3, 5 with the heights 1, 3, 6, 4. Another jump sequence of length 4 is 1, 2, 4, 5.
dp, dp[i]=max(dp[j])+1, 그 중에서 |h[i]-h[j]|>=d 데이터가 좀 크고 이산화된 다음에 라인 트리로 최적화한 다음에 마지막에 출력을 귀속적으로 구해낸다. 전체적으로 보면 매우 간단한 문제이다.

#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;
int dp[N];
int cnt, n, d;
__int64 xis[N];
__int64 arr[N];
struct node
{
	int l, r;
	int val;
}tree[N << 2];

int binsearch(__int64 x)
{
	int l = 1, r = cnt, mid;
	while (l <= r)
	{
		mid = (l + r) >> 1;
		if (xis[mid] == x)
		{
			break;
		}
		else if (xis[mid] > x)
		{
			r = mid - 1;
		}
		else
		{
			l = mid + 1;
		}
	}
	return mid;
}

int left_binsearch(__int64 x)
{
	int l = 1, r = cnt, mid, ans = -1;
	while (l <= r)
	{
		mid = (l + r) >> 1;
		if (xis[mid] <= x)
		{
			ans = mid;
			l = mid + 1;
		}
		else
		{
			r = mid - 1;
		}
	}
	return ans;
}

int right_binsearch(__int64 x)
{
	int l = 1, r = cnt, mid, ans = -1;
	while (l <= r)
	{
		mid = (l + r) >> 1;
		if (xis[mid] >= x)
		{
			ans = mid;
			r = mid - 1;
		}
		else
		{
			l = mid + 1;
		}
	}
	return ans;
}

void build(int p, int l, int r)
{
	tree[p].l = l;
	tree[p].r = r;
	tree[p].val = 0;
	if (l == r)
	{
		return;
	}
	int mid = (l + r) >> 1;
	build(p << 1, l, mid);
	build(p << 1 | 1, mid + 1, r);
}

void update(int p, int pos, int val)
{
	if (tree[p].l == tree[p].r)
	{
		tree[p].val = max(tree[p].val, val);
		return;
	}
	int mid = (tree[p].l + tree[p].r) >> 1;
	if (pos <= mid)
	{
		update(p << 1, pos, val);
	}
	else
	{
		update(p << 1 | 1, pos, val);
	}
	tree[p].val = max(tree[p << 1].val, tree[p << 1 | 1].val);
}

int query(int p, int l, int r)
{
	if (tree[p].l >= l && tree[p].r <= r)
	{
		return tree[p].val;
	}
	int mid = (tree[p].l + tree[p].r) >> 1;
	if (r <= mid)
	{
		return query(p << 1, l, r);
	}
	else if (l > mid)
	{
		return query(p << 1 | 1, l, r);
	}
	else
	{
		return max(query(p << 1, l, mid), query(p << 1 | 1, mid + 1, r));
	}

}

void dfs(int i)
{
	if (dp[i] == 1)
	{
		return;
	}
	for (int j = i - 1; j >= 1; --j)
	{
		if (dp[i] == dp[j] + 1 && abs(arr[i] - arr[j]) >= d)
		{
			dfs(j);
			printf("%d ", j);
			break;
		}
	}
}

int main()
{
	while(~scanf("%d%d", &n, &d))
	{
		int tmp = 0;
		memset (dp, 0, sizeof(dp));
		cnt = 0;
		for (int i = 1; i <= n; ++i)
		{
			scanf("%I64d", &arr[i]);
			xis[++cnt] = arr[i];
		}
		sort (xis + 1, xis + cnt + 1);
		cnt = unique(xis + 1, xis + cnt + 1) - xis - 1;
		build(1, 1, cnt);
		for (int i = 1; i <= n; ++i)
		{
			int l = left_binsearch(arr[i] - d);
			int r = right_binsearch(arr[i] + d);
			if (l < 0 && r < 0)
			{
			 	dp[i] = 1;
			}
			else if (r < 0)
			{
				dp[i] = max(1, query(1, 1, l) + 1);
			}
			else if (l < 0)
			{
				dp[i] = max(1, query(1, r, cnt) + 1);
			}
			else
			{
				dp[i] = max(query(1, 1, l), query(1, r, cnt)) + 1;
			}
			tmp = max(tmp, dp[i]);
			int cur = binsearch(arr[i]);
			update(1, cur, dp[i]);
		}
		printf("%d
", tmp);
		for (int i = 1; i <= n; ++i)
		{
			if (tmp == dp[i])
			{
				dfs(i);
				printf("%d
", i);
				break;
			}
		}
	}
	return 0;
}