比赛 |
防止浮躁的小练习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;
}