Codeforces Round #643 (Div. 2) C.Count Triangles

Codeforces Round #643 (Div. 2) C.Count Triangles
タイトルリンクLike any unknown mathematician,Yuri has favourite numbers:A,B,C,and D,where A≦B≦C≦D.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 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≤5e5) — 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 holds.
Examples
input

1 2 3 4

output

4

input

1 2 2 5

output

3

input

500000 500000 500000 500000

output

1

Dをやっていることを知っていたが、試合後Dの過題人数はCの2倍で、本当にこの問題を吐いたらO(n)のアルゴリズムを考えなければならない.つまり、1つの区間しか考えられない.私が選んだのは[A,B][A,B][A,B]~つまり[A,B][A,B][A,B]から1つの辺i i i iを最小辺として選んだ.次に,区間[B,C][B,C][B,C][B,C]から最大辺の範囲である[B+i−1,C+i−1][B+i−1,C+i−1][B+i−1][B+i−1,C+i−1]を求めることができ,以下は区間[C,D][C,D][C,D]と交差するS S S S S S Sを取ることであり,交差するS S S Sは求和式を通じて迅速に計算できることがわかり,以下は両極端な状況を考慮する.B+i−1≧D B+i−1geq D B+i−1≧Dの場合、答えa n s=a n s+(D−C+1)∗(C−B+1)ans=ans+(D−C+1)*(C−B+1)ans=ans+(D−C+1)∗(C−B+1)2.C+i−1≧D C+i−1geq D C+i−1≧Dの場合,答えa n s=a n s+(D−C+1)∗(C+i−1−D)ans=ans+(D−C+1)*(C+i−1−D)ans=ans+(D−C+1)∗(C+i−1−D)ACコードは次のようになる.

#include
using namespace std;
typedef long long ll;

main(){
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    ll ans=0;
    for(ll i=a;i<=b;i++){
        ll mn=i+b-1,mx=i+c-1;
        if(mn>=d) ans+=(d-c+1)*(c-b+1);
        else{
            ll l=max(mn,c),r=min(d,mx);
            ans+=(r-l+1)*(l-c+1+r-c+1)/2;
            if(mx>d) ans+=(mx-d)*(d-c+1);
        }
    }
     cout<<ans;
}