比赛 |
防止浮躁的小练习v0.9 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
题目名称 |
__卡片游戏 |
最终得分 |
100 |
用户昵称 |
ZXCVBNM_1 |
运行时间 |
6.050 s |
代码语言 |
C++ |
内存使用 |
30.83 MiB |
提交时间 |
2016-11-07 19:57:11 |
显示代码纯文本
#include<bits/stdc++.h>
#define LL long long
#define MAXN 500010
using namespace std;
LL a[MAXN],sum1[MAXN],sum2[MAXN],c1[MAXN],c2[MAXN],w1[MAXN],w2[MAXN],NN,BIT[MAXN];
LL Gcd(LL aa,LL bb){if(bb==0LL)return aa;else return Gcd(bb,aa%bb);}
LL read()
{
LL s=0,fh=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')fh=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=s*10+(ch-'0');ch=getchar();}
return s*fh;
}
LL Lowbit(LL k){return k&(-k);}
void Update(LL k1,LL k2)
{
while(k1<=NN)
{
BIT[k1]+=k2;
k1+=Lowbit(k1);
}
}
LL Query(LL k1)
{
LL sum=0LL;
while(k1>0LL)
{
sum+=BIT[k1];
k1-=Lowbit(k1);
}
return sum;
}
int main()
{
freopen("xgame.in","r",stdin);
freopen("xgame.out","w",stdout);
LL N,L,R,i,lc1,lc2,ans1,ans2,ans3,ans4,gcd,N1;
N=read();L=read();R=read();
for(i=1;i<=N;i++)a[i]=read();
for(i=1;i<=N;i++)
{
c1[i+1]=sum1[i+1]=sum1[i]+(a[i]-L);
c2[i+1]=sum2[i+1]=sum2[i]+(a[i]-R);
}
N1=N+1;
sort(c1+1,c1+N1+1);
sort(c2+1,c2+N1+1);
lc1=unique(c1+1,c1+N1+1)-(c1+1);
lc2=unique(c2+1,c2+N1+1)-(c2+1);
for(i=1;i<=N1;i++)
{
w1[i]=lower_bound(c1+1,c1+lc1+1,sum1[i])-c1;
w2[i]=lower_bound(c2+1,c2+lc2+1,sum2[i])-c2;
}
ans1=0LL;ans2=0LL;
memset(BIT,0,sizeof(BIT));
NN=lc1;
for(i=1;i<=N1;i++)
{
ans1+=Query(w1[i]);
Update(w1[i],1LL);
}
memset(BIT,0,sizeof(BIT));
NN=lc2;
for(i=N1;i>=1;i--)
{
ans2+=Query(w2[i]);
Update(w2[i],1LL);
}
ans4=((1+N)*N)/2LL;
ans3=ans1+ans2-ans4;
gcd=Gcd(ans3,ans4);
ans3/=gcd;ans4/=gcd;
if(ans3==0LL)printf("0");
else if(ans3==ans4)printf("1");
else printf("%lld/%lld",ans3,ans4);
fclose(stdin);
fclose(stdout);
return 0;
}