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