← 返回题目列表

Codeforces · 1355/C

C. 计算三角形

中文机器翻译题面 查看原题

像任何不知名的数学家一样,尤里有最喜欢的数字:$$$A$$$、$$$B$$$、$$$C$$$ 和 $$$D$$$,其中 $$$A \leq B \leq C \leq D$$$。 Yuri 也喜欢三角形,有一次他想:存在多少个具有整数边 $$$x$$$、$$$y$$$ 和 $$$z$$$ 的非退化三角形,使得 $$$A \leq x \leq B \leq y \leq C \leq z \leq D$$$ 成立?

Yuri现在正在为新的比赛准备问题,所以他很忙。这就是为什么他要求你计算具有所描述的属性的三角形的数量。

当且仅当其顶点不共线时,三角形才被称为非退化三角形。

输入

第一行包含四个整数:$$$A$$$、$$$B$$$、$$$C$$$ 和 $$$D$$$ ($$$1 \leq A \leq B \leq C \leq D \leq 5 \cdot 10^5$$$) — Yuri 最喜欢的数字。

输出

打印具有整数边 $$$x$$$、$$$y$$$ 和 $$$z$$$ 的非退化三角形的数量,使得不等式 $$$A \leq x \leq B \leq y \leq C \leq z \leq D$$$ 成立。

示例

输入 #1

1 2 3 4

输出 #1

4

输入 #2

1 2 2 5

输出 #2

3

输入 #3

500000 500000 500000 500000

输出 #3

1

注意

在第一个示例中,Yuri 可以组成边为 $$$(1, 3, 3)$$$、$$$(2, 2, 3)$$$、$$$(2, 3, 3)$$$ 和 $$$(2, 3, 4)$$$ 的三角形。

在第二个示例中,Yuri 可以组成边为 $$$(1, 2, 2)$$$、$$$(2, 2, 2)$$$ 和 $$$(2, 2, 3)$$$ 的三角形。

在第三个示例中,Yuri 只能组成一个边长等于 $$$5 \cdot 10^5$$$ 的等边三角形。