1 solutions

  • 0
    @ 2024-12-11 0:33:47

    C++ :

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    #define MAXN 1000000+5
    long A[MAXN],B[MAXN],tmp[MAXN];
    long n,L,R;
    long long P,Q,Ans,ans;
    void read(long &x){
        char ch;
        for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
        x=ch-'0';
        for(ch=getchar();ch>='0'&&ch<='9';ch=getchar())x=10*x+ch-'0';
    }
    long long gcd(long long a,long long b){
        return(!(a%b))?(b):(gcd(b,a%b));
    }
    void count1(long *a,long *b,long l,long r){
        if(l==r)return;
        long mid=(l+r)>>1;
        count1(a,b,l,mid);
        count1(a,b,mid+1,r);
        long i=l,j=mid+1,k=l-1;
        while(i<=mid && j<=r){
            while(a[i]<a[j] && i<=mid){
                b[++k]=a[i];
                if(j<=r)ans+=j-mid-1;
                i++;
            }
            while(a[i]>=a[j] && j<=r){
                b[++k]=a[j];
                j++;
            }
        }
        while(i<=mid){
            b[++k]=a[i];
            ans+=j-mid-1;
            i++;
        }
        for(long i=l;i<=j-1;i++)a[i]=b[i];
    }
    void count2(long *a,long *b,long l,long r){
        if(l==r)return;
        long mid=(l+r)>>1;
        count2(a,b,l,mid);
        count2(a,b,mid+1,r);
        long i=l,j=mid+1,k=l-1;
        while(i<=mid && j<=r){
            while(a[i]<=a[j] && i<=mid){
                b[++k]=a[i];
                if(j<=r)ans+=j-mid-1;
                i++;
            }
            while(a[i]>a[j] && j<=r){
                b[++k]=a[j];
                j++;
            }
        }
        while(i<=mid){
            b[++k]=a[i];
            ans+=j-mid-1;
            i++;
        }
        for(long i=l;i<=j-1;i++)a[i]=b[i];
    }
    int main()
    {
    	//freopen("game.in","r",stdin);
    	//freopen("game.out","w",stdout);
        read(n);read(L);read(R);
        long sum=0;
        long t;
        A[0]=B[0]=0;
        for(long i=1;i<=n;i++){
            read(t);
            sum+=t;
            A[i]=L*i-sum;
            B[i]=R*i-sum;
        }
        ans=0;
        count1(A,tmp,0,n);
        Ans=ans;
        ans=0;
        count2(B,tmp,0,n);
        Ans-=ans;
        P=Ans;
        Q=(n*1LL/2)*(n*1LL+1LL);
        long long m=gcd(P,Q);
        cout<<P/m<<"/"<<Q/m<<endl;
        return 0;
    }
    
    
    • 1

    Information

    ID
    720
    Time
    1000ms
    Memory
    128MiB
    Difficulty
    (None)
    Tags
    # Submissions
    0
    Accepted
    0
    Uploaded By