比赛 |
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;
}