记录编号	338334	评测结果	RRRRRRRRRRRRRRRRRRRR
题目名称	__卡片游戏	最终得分	0
用户昵称	404	是否通过	未通过
代码语言	C++	运行时间	0.029 s
提交时间	2016-11-05 09:58:05	内存使用	29.32 MiB

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#define ll long long
using namespace std;
const int mod=100000007;
ll n,l,r,cnt,res;
ll a[500500],s[500500],al[500500],ar[500500],sl[500050],sr[500500],tmp[500500],tmp2[500500];
ll gcd(ll a,ll b){if(a%b==0)return b;return gcd(b,a%b);}
void work1()
{
	ll y=(ll)(n+1)*(ll)(n)/2;
	ll ans=0;
	for(int i=1;i<=n;i++)
	   for(int j=i;j<=n;j++)
		  if(l*(j-i+1)<=s[j]-s[i-1]&&r*(j-i+1)>=s[j]-s[i-1])
			ans++;
	if(ans==0){printf("0");return;}
	ll fff=gcd(ans,y);
	ans=ans/fff,y=y/fff;
	if(ans!=y)printf("%I64d/%I64d\n",ans,y);
	else printf("1\n");
}
void mergesort1(int start,int mid,int end)
{
	int i = start;  
    int j = mid+1;  
    int k = start;  
    while(i <= mid && j <= end)  
    {  
        if(a[i] > a[j])
		{
			
			tmp[k++] = sr[j++];  
		}
        else  
        {  
            res += mid - i + 1;
            tmp[k++] = a[i++];  
        }  
    }  
    while(i <= mid) tmp[k++] = sr[i++];  
    while(j <= end) tmp[k++] = sr[j++];  
    for(int i=start;i<=end;i++)sr[i]=tmp[i];  
}
void mergesort2(int start,int mid,int end)
{
	int i = start;  
    int j = mid+1;  
    int k = start;  
    while(i <= mid && j <= r)  
    {  
        if(sl[i]>sl[j])  
        {  
            tmp[k++] = sl[j++];  
            res += mid - i + 1;
        }  
        else  tmp[k++] = sl[i++];  
    }  
    while(i <= mid) tmp[k++] = sl[i++];  
    while(j <= end) tmp[k++] = sl[j++];  
    for(int i=start;i<=end;i++)sl[i]=tmp[i];  
}
void merge1(int start,int end)
{
	if(start<end)
	{
		int mid=(start+end)/2;
		merge1(start,mid);
		merge1(mid+1,end);
		mergesort1(start,mid,end);
	}
}
void merge2(int start,int end)
{
	if(start<end)
	{
		int mid=(start+end)/2;
		merge1(start,mid);
		merge1(mid+1,end);
		mergesort2(start,mid,end);
	}
}
void work2()
{
	 ll y=(ll)(n+1)*(ll)(n)/2;
	 for(int i=1;i<=n;i++)al[i]=a[i]-l,ar[i]=a[i]-r;
	 for(int i=1;i<=n;i++)sl[i]=sl[i-1]+al[i],sr[i]=sr[i-1]+ar[i];
	 merge1(1,n);ll ans=0;
	 ans+=res;res=0;
	 merge2(1,n);
	 ans+=(res);
	 if(ans==0){printf("0");return;}
	 ll fff=gcd(ans,y);
	 ans=ans/fff,y=y/fff;
	 if(ans!=y)printf("%I64d/%I64d\n",ans,y);
	 else printf("1\n");
}
int main()
{
	freopen("xnumber.in","r",stdin);
	freopen("xnumber.out","w",stdout);
    scanf("%I64d%I64d%I64d",&n,&l,&r);
    for(int i=1;i<=n;i++)scanf("%I64d",&a[i]),s[i]=s[i-1]+a[i];
    if(n<=10000){work1();return 0;}
    else{work2();return 0;}
    //work2();
}