Count Triangles

Like any unknown mathematician, Yuri has favourite numbers: A, B, C, and D, where A ≤ B ≤ C ≤ D A≤B≤C≤D ABCD. Yuri also likes triangles and once he thought: how many non-degenerate triangles with integer sides x, y, and z exist, such that A ≤ x ≤ B ≤ y ≤ C ≤ z ≤ D A≤x≤B≤y≤C≤z≤D AxByCzD holds?

Yuri is preparing problems for a new contest now, so he is very busy. That’s why he asked you to calculate the number of triangles with described property.

The triangle is called non-degenerate if and only if its vertices are not collinear.

Input
The first line contains four integers: A, B, C and D ( 1 ≤ A ≤ B ≤ C ≤ D ≤ 5 ⋅ 1 0 5 1≤A≤B≤C≤D≤5⋅10^5 1ABCD5105) — Yuri’s favourite numbers.

Output
Print the number of non-degenerate triangles with integer sides x, y, and z such that the inequality A ≤ x ≤ B ≤ y ≤ C ≤ z ≤ D A≤x≤B≤y≤C≤z≤D AxByCzD holds.

Examples

input
1 2 3 4
output
4
input
1 2 2 5
output
3
input
500000 500000 500000 500000
output
1

Note
In the first example Yuri can make up triangles with sides (1,3,3), (2,2,3), (2,3,3) and (2,3,4).

In the second example Yuri can make up triangles with sides (1,2,2), (2,2,2) and (2,2,3).

In the third example Yuri can make up only one equilateral triangle with sides equal to 5 ⋅ 1 0 5 5⋅10^5 5105.
由于三角形三条边的大小关系已经确定,因此可以求出两条较短边长度和的取值范围为 [ m a x ( C + 1 , A + B ) , B + C ] [max(C+1,A+B),B+C] [max(C+1,A+B),B+C]
若两条较短边长度和 i i i,则不难得出最长边长度的取值范围为 [ C , m i n ( D , i − 1 ) ] [C,min(D,i-1)] [C,min(D,i1)]
设最短边为 x x x,则:
{ A ≤ x ≤ B B ≤ i − x ≤ C \left\{ \begin{aligned} A≤x≤B \\ B≤i-x≤C\\ \end{aligned} \right. {AxBBixC
因此 x x x的取值范围为 [ m a x ( A , i − C ) , m i n ( B , i − B ) ] [max(A,i-C),min(B,i-B)] [max(A,iC),min(B,iB)]
枚举 i i i的取值,将两个区间长度相乘累加到 a n s ans ans中即可得到答案。

#includebits/stdc++.h

#define si(a) scanf("%d",a)
#define sl(a) scanf("%lld",a)
#define sd(a) scanf("%lf",a)
#define sc(a) scahf("%c",a);
#define ss(a) scanf("%s",a)
#define pi(a) printf("%d\n",a)
#define pl(a) printf("%lld\n",a)
#define pc(a) putchar(a)
#define ms(a) memset(a,0,sizeof(a))
#define repi(i, a, b) for(register int i=a;i=b;++i)
#define repd(i, a, b) for(register int i=a;i=b;--i)
#define reps(s) for(register int i=head[s];i;i=Next[i])
#define ll long long
#define ull unsigned long long
#define vi vectorint
#define pii pairint,int
#define mii unordered_mapint,int
#define msi unordered_mapstring,int
#define lowbit(x) ((x)(-(x)))
#define ce(i, r) i==r?'\n':' '
#define pb push_back
#define fi first
#define se second
#define INF 0x3f3f3f3f
#define pr(x) cout#x": "xendl
using namespace std;

inline int qr() {
    int f = 0, fu = 1;
    char c = getchar();
    while (c  '0' || c  '9') {
        if (c == '-')fu = -1;
        c = getchar();
    }
    while (c = '0'  c = '9') {
        f = (f  3) + (f  1) + c - 48;
        c = getchar();
    }
    return f * fu;
}

int A, B, C, D;

int main() {
    A = qr(), B = qr(), C = qr(), D = qr();
    ll ans = 0;
    repi(i, max(C + 1, A + B), B + C)
    ans += 1ll * (min(D, i - 1) - C + 1) * (min(B, i - B) - max(A, i - C) + 1);
    pl(ans);
    return 0;
}
最新回复(0)
/jishuAluC_2BC_2FR6lpsuZBIyUICYHvhMy6e0q3GBUSXHA_3D_3D4795024
8 简首页