比赛 防止浮躁的小练习v0.9 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 __卡片游戏 最终得分 100
用户昵称 Lethur 运行时间 5.640 s
代码语言 C++ 内存使用 23.20 MiB
提交时间 2016-11-07 20:00:50
显示代码纯文本
    #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;
    }