比赛 防止浮躁的小练习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;
}