比赛 |
noip |
评测结果 |
RRRRRRRRRRRRRRRRRRRR |
题目名称 |
__卡片游戏 |
最终得分 |
0 |
用户昵称 |
404 |
运行时间 |
0.030 s |
代码语言 |
C++ |
内存使用 |
29.32 MiB |
提交时间 |
2016-11-04 21:53:46 |
显示代码纯文本
#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();
}