记录编号	338292	评测结果	AAAAATTTTTATTTTTTTTT
题目名称	__卡片游戏	最终得分	30
用户昵称	goodqt	是否通过	未通过
代码语言	C++	运行时间	29.251 s
提交时间	2016-11-05 09:46:44	内存使用	2.22 MiB

#include <cstdio>
#include <iostream>
#include <set>

int n,l,r;
int sequence[500050];
std::multiset<int> set;

long long gcd(long long a,long long b)
{
	if(a == 0 || b == 0)
		return a + b;
	return gcd(b,a % b);
}

long long solve1(int x)
{
	int i;
	int sum;
	long long answer;
	std::multiset<int>::iterator z;
	
	if(x < 0)
		return 0;
	
	set.clear();
	set.insert(0);
	
	sum = 0;
	answer = 0;
	for(i = 0;i < n;++i)
	{
		sum += sequence[i] - x;
		set.insert(sum);
		
		z = set.lower_bound(sum);
		answer += std::distance(z,set.end()) - 1;
	}
	
	return answer;
}

long long solve2(int x)
{
	int i;
	int sum;
	long long answer;
	std::multiset<int>::iterator z;
	
	if(x < 0)
		return 0;
	
	set.clear();
	set.insert(0);
	
	sum = 0;
	answer = 0;
	for(i = 0;i < n;++i)
	{
		sum += sequence[i] - x;
		set.insert(sum);
		
		z = set.upper_bound(sum);
		answer += std::distance(z,set.end());
	}
	
	return answer;
}

int main(void)
{	
	int i;
	long long result;
	long long all;
	long long x;

	freopen("xgame.in","r",stdin);
	freopen("xgame.out","w",stdout);

	scanf("%d %d %d",&n,&l,&r);
	
	for(i = 0;i < n;++i)
		scanf("%d",&sequence[i]);
	
	all = 1ll * n * (n - 1) / 2 + n;
	result = solve1(r) - solve2(l);
	
	if(!result){
		puts("0");
		return 0;
	}else if(result == all){
		puts("1");
		return 0;
	}
	
	x = gcd(all,result);
	all /= x;
	result /= x;
	
	std::cout<<result<<"/"<<all<<std::endl;
	//printf("%I64d/%I64d\n",result,all);	
}