Skip to content

1245: 元组统计

题目

题目描述

现在给定一个 $n$ 个元素的数组 $A$,以及 $x, y$ 两个数字,我们希望找到三元组 $(i,j,k)$ 满足以下条件: 1. $1 <= i < j < k <= n$ 2. $|A[i] - A[j]| <= x$ 3. $|A[j] - A[k]| <= y$

你需要统计满足条件的三元组 $(i, j, k)$ 的数量。

输入格式

第一行的输入 $n, x, y$

第二行输入 $n$ 个整数,表示这一个数组 $A$

输出格式

第一行的输出一个整数,表示满足条件的三元组个数,答案对 $1000000007$ 取模

样例输入

样例输入 1

text 5 3 3 7 1 8 9 0

样例输入 2

text 10 5 4 7 0 9 6 4 2 6 4 7 3

样例输出

样例输出 1

text 1

样例输出 2

text 83

数据范围

对于 $30\%$ 的数据,满足 $1 \leq n \leq 2\times 10^2$

对于 $60\%$ 的数据,满足 $1 \leq n \leq 2\times 10^3$

对于 $100\%$ 的数据,满足 $1 \leq n \leq 2\times 10^5$,且所有输入的数字都是 $[0, 10^9]$ 之间的非负整数,数据随机。

时间限制:1000 ms 空间限制:512 mb

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!