Triple

Triple

测试数据来自 system/1863

描述

序列 A 包含 N 个整数 a1, a2, …, an。
对于每个整数 ai,请统计有多少个整数三元组 (j, k, l) 满足 max{0, i–D} < j <= k <= l < i
并且 aj + ak + al = ai. 其中 D 是一个常数。
依次输出对每个整数 ai(1 <= i <= N) 的答案。

格式

输入格式

第一行,两个整数 N, D。
第二行,N 个整数,依次是 a1, a2, …, an.

输出格式

输出 N 行,每行一个整数,依次表示对每个整数 ai 的答案。

样例1

样例输入1

6 5
4 1 0 -1 3 2

样例输出1

0
0
0
0
2
2

限制

30% 的数据:1 <= N <= 200.
此外有 30% 的数据:1 <= N, Ai <= 2,000.
100% 的数据:1 <= N <= 5,000,1 <= D <= N,|Ai| <= 106.

提示

对 a1 = 4,a2 = 1,a3 = 0,a4 = -1 不存在任何三元组。
对 a5 = 3,满足条件的三元组有 (1, 3, 4),(2, 2, 2)。
对 a6 = 2,满足条件的三元组有 (2, 2, 3),(3, 4, 5)。

来源

BJOI 2014 Day 1

信息

ID
1888
难度
(无)
分类
(无)
标签
递交数
0
已通过
0
通过率
?
上传者