比赛 noip 评测结果 AAAAAAAAAAAAAAAATTTA
题目名称 __卡片游戏 最终得分 85
用户昵称 _Itachi 运行时间 12.073 s
代码语言 C++ 内存使用 8.84 MiB
提交时间 2016-11-04 21:36:28
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
const int maxn=500005;
LL Rabit_gcd(LL a,LL b){return b?Rabit_gcd(b,a%b):a;}
int n,l,r,a[maxn],H=0;
struct Rabit_tree{int x,th,sum;}e[maxn];
bool Rabit_comps(Rabit_tree a,Rabit_tree b){return a.sum<b.sum;}
bool Rabit_compx(Rabit_tree a,Rabit_tree b){return a.x<b.x;}
bool Rabit_in(){
	scanf("%d%d%d",&n,&l,&r);int i;bool f1=true,f2=true;
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]),e[i].x=i,
		f1&=(l<=a[i]&&a[i]<=r),f2&=(a[i]<l||a[i]>r);	
	if(f1){puts("1");return true;}
	if(f2){puts("0");return true;}
	return false;
}
#define _low (i&(-i))
int c[maxn];
void Rabit_add(int i){
	for(;i<=H;i+=_low)c[i]++;
}
int Rabit_get(int i){
	int res=0;for(;i;i-=_low)res+=c[i];return res;
}
void Rabit_ans(){
	LL cnt=0,cnt2=0,cot=(n*1ll*(n+1ll))>>1,g;int v,i;
	for(i=1;i<=n;i++)e[i].sum=e[i-1].sum+a[i]-l;
	sort(e,e+n+1,Rabit_comps);e[0].th=H=1;
	for(i=1;i<=n;i++)e[i].th=H=H+(e[i].sum!=e[i-1].sum);
	sort(e,e+n+1,Rabit_compx);
	Rabit_add(e[0].th);
	for(i=1;i<=n;i++){
		Rabit_add(e[i].th);	
		cnt+=i+1-Rabit_get(e[i].th);
	}
	memset(c,0,sizeof(c));
	for(i=1;i<=n;i++)e[i].sum=e[i-1].sum+a[i]-r;
	sort(e,e+n+1,Rabit_comps);e[0].th=H=1;
	for(i=1;i<=n;i++)e[i].th=H=H+(e[i].sum!=e[i-1].sum);
	sort(e,e+n+1,Rabit_compx);
	Rabit_add(e[0].th);
	for(i=1;i<=n;i++){
		Rabit_add(e[i].th);	
		cnt+=Rabit_get(e[i].th-1);
	}
	cnt=cot-cnt;
	g=Rabit_gcd(cnt,cot);
	cnt/=g,cot/=g;
	printf("%lld/%lld\n",cnt,cot);
}
void Rabit_main(){
	if(!Rabit_in())Rabit_ans();
}
int main(){
#define _Rabit _RABIT
#ifdef _Rabit
	freopen("xgame.in","r",stdin);
	freopen("xgame.out","w",stdout);
#endif
	Rabit_main();
#ifndef _Rabit
	getchar(),getchar();
#endif
	fclose(stdin);fclose(stdout);
	return 0;
}