#P18786. [KOI2026 一轮] 跳跃

[KOI2026 一轮] 跳跃

[KOI2026 一轮] 跳跃(점프 / Jump)

题目描述

二维平面上有 NN 个踏板,编号为 1,2,…,N1,2,\ldots,N。踏板 ii 位于点 (Xi,i)(X_i,i)。

给定正整数 DD。只有同时满足下列条件时,才能从踏板 ii 跳到踏板 jj:

  • i<ji<j;
  • ∣Xi−Xj∣≤D|X_i-X_j|\le D。

对于每个踏板 ii,求从它出发,经过零次或多次跳跃后能够到达的不同踏板数量。起点自身也要计入答案。

输入格式

第一行两个整数 N,DN,D。

第二行 NN 个整数 X1,X2,…,XNX_1,X_2,\ldots,X_N。

输出格式

输出一行 NN 个整数。第 ii 个数表示从踏板 ii 出发能够到达的不同踏板数量。

样例 1

6 2
3 5 4 6 1 3
6 4 3 1 2 1

各起点的可达踏板集合分别为:{1,2,3,4,5,6}\{1,2,3,4,5,6\}、{2,3,4,6}\{2,3,4,6\}、{3,4,6}\{3,4,6\}、{4}\{4\}、{5,6}\{5,6\}、{6}\{6\}。

样例 2

6 3
1 4 8 9 10 15
2 1 3 2 1 1

样例 3

3 2
1 4 7
1 1 1

数据范围与子任务

所有输入均为整数。

  • 1≤N≤3000001\le N\le300000;
  • 1≤D≤1091\le D\le10^9;
  • 1≤Xi≤1091\le X_i\le10^9。
子任务 分值 附加限制
1 12 N≤300N\le300
2 32 N≤7500N\le7500
3 9 X1≤X2≤⋯≤XNX_1\le X_2\le\cdots\le X_N
4 23 所有 Xi≤30X_i\le30
5 33 D=1D=1
6 41 无附加限制

原题满分为 150 分;本资料包保留原子任务及分值。时限 2 秒,内存限制 1024 MiB。