记录编号	337901	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	__卡片游戏	最终得分	100
用户昵称	Lethur	是否通过	通过
代码语言	C++	运行时间	4.294 s
提交时间	2016-11-04 22:03:41	内存使用	23.20 MiB

    #include <queue>
    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    typedef long long ll;
    inline void read(ll &x){
    	x=0;char ch;bool flag = false;
    	while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
    	while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
    }
    inline ll cat_max(const ll &a,const ll &b){return a>b ? a:b;}
    inline ll cat_min(const ll &a,const ll &b){return a<b ? a:b;}
    const ll maxn = 500010;
    ll gcd(const ll &a,const ll &b){return b == 0 ? a : gcd(b,a%b);}
    ll c[maxn];
    ll sum1[maxn],sum2[maxn];
    ll t1[maxn],t2[maxn],n;
    #define lowbit(x) x&-x
    ll C[maxn];
    inline ll query(ll i){
    	ll ret = 0;
    	for(ll x = i;x;x-=lowbit(x)) ret += C[x];
    	return ret;
    }
    inline void add(ll i){
    	for(ll x = i;x<=n;x+=lowbit(x)) ++C[x];
    }
    int main(){
    	freopen("xgame.in","r",stdin);
    	freopen("xgame.out","w",stdout);
    	ll l,r;read(n);read(l);read(r);
    	for(ll i=1;i<=n;++i) read(c[i]);
    	for(ll i=1;i<=n;++i){
    		sum1[i] = sum1[i-1] + c[i] - l;
    		sum2[i] = sum2[i-1] + c[i] - r;
    		t1[i] = sum1[i];t2[i] = sum2[i];
    	}sort(t1+1,t1+n+2);sort(t2+1,t2+n+2);
    	for(ll i=0;i<=n;++i){
    		sum1[i] = lower_bound(t1+1,t1+n+2,sum1[i]) - t1;
    		sum2[i] = lower_bound(t2+1,t2+n+2,sum2[i]) - t2;
    	}
    	ll m = (n*(n+1))>>1;
    	ll ans = 0;
    	//puts("");
    	add(sum1[0]);
    	for(ll i=1;i<=n;++i){
    		ans += i - query(sum1[i]);
    		add(sum1[i]);
    	}
    	memset(C,0,sizeof C);
    	add(sum2[0]);
    	for(ll i=1;i<=n;++i){
    		ans += query(sum2[i] - 1) ;
    		add(sum2[i]);
    	}
    	ans = m - ans;
    	ll x = gcd(ans,m);
    	m /= x;ans /= x;
    	if(ans == 0) printf("0");
    	else if(m == ans) printf("1");
    	else printf("%lld/%lld",ans,m);
    	getchar();getchar();
    	return 0;
    }