记录编号 |
337862 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
题目名称 |
__卡片游戏 |
最终得分 |
100 |
用户昵称 |
哒哒哒哒哒! |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
3.584 s |
提交时间 |
2016-11-04 21:44:03 |
内存使用 |
9.87 MiB |
显示代码纯文本
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;
#define ll long long
int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*f;
}
const int maxn=501000;
int C[maxn],s1[maxn],s2[maxn],a[maxn];
int c[maxn],n,l,r;
void add(int x,int y){for(int i=x;i<=n+10;i+=(i&-i))c[i]+=y;}
ll query(int x){ll s=0;for(int i=x;i;i-=i&-i)s+=c[i];return s;}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
int main(){
freopen("xgame.in","r",stdin);freopen("xgame.out","w",stdout);
n=read(),l=read(),r=read();
for(int i=1;i<=n;i++) C[i]=read();
for(int i=1;i<=n;i++) s1[i]=s1[i-1]+C[i]-l;
for(int i=1;i<=n;i++) s2[i]=s2[i-1]+C[i]-r;
for(int i=1;i<=n;i++)a[i]=s1[i];
sort(a+1,a+n+2);
for(int i=0;i<=n;i++)s1[i]=lower_bound(a+1,a+n+2,s1[i])-a;
ll ans=0;
add(s1[0],1);
for(int i=1;i<=n;i++){
ans+=i-query(s1[i]);
add(s1[i],1);
}
memset(a,0,sizeof a);
memset(c,0,sizeof c);
for(int i=1;i<=n;i++)a[i]=s2[i];
sort(a+1,a+n+2);
for(int i=0;i<=n;i++)s2[i]=lower_bound(a+1,a+n+2,s2[i])-a;
add(s2[0],1);
for(int i=1;i<=n;i++){
ans+=query(s2[i]-1);
add(s2[i],1);
}
ll A=(ll)n*(n+1)/2-ans;
ll B=(ll)n*(n+1)/2;
if(A==0) printf("0\n");
else if(A==B) printf("1\n");
else{
ll x=gcd(A,B);
printf("%lld/%lld\n",A/x,B/x);
}
fclose(stdin);fclose(stdout);
return 0;
}