1 solutions
-
0
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