比赛 防止浮躁的小练习v0.9 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 __卡片游戏 最终得分 100
用户昵称 Lethur 运行时间 5.640 s
代码语言 C++ 内存使用 23.20 MiB
提交时间 2016-11-07 20:00:50
显示代码纯文本
  1. #include <queue>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <iostream>
  5. #include <algorithm>
  6. using namespace std;
  7. typedef long long ll;
  8. inline void read(ll &x){
  9. x=0;char ch;bool flag = false;
  10. while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
  11. while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
  12. }
  13. inline ll cat_max(const ll &a,const ll &b){return a>b ? a:b;}
  14. inline ll cat_min(const ll &a,const ll &b){return a<b ? a:b;}
  15. const ll maxn = 500010;
  16. ll gcd(const ll &a,const ll &b){return b == 0 ? a : gcd(b,a%b);}
  17. ll c[maxn];
  18. ll sum1[maxn],sum2[maxn];
  19. ll t1[maxn],t2[maxn],n;
  20. #define lowbit(x) x&-x
  21. ll C[maxn];
  22. inline ll query(ll i){
  23. ll ret = 0;
  24. for(ll x = i;x;x-=lowbit(x)) ret += C[x];
  25. return ret;
  26. }
  27. inline void add(ll i){
  28. for(ll x = i;x<=n;x+=lowbit(x)) ++C[x];
  29. }
  30. int main(){
  31. freopen("xgame.in","r",stdin);
  32. freopen("xgame.out","w",stdout);
  33. ll l,r;read(n);read(l);read(r);
  34. for(ll i=1;i<=n;++i) read(c[i]);
  35. for(ll i=1;i<=n;++i){
  36. sum1[i] = sum1[i-1] + c[i] - l;
  37. sum2[i] = sum2[i-1] + c[i] - r;
  38. t1[i] = sum1[i];t2[i] = sum2[i];
  39. }sort(t1+1,t1+n+2);sort(t2+1,t2+n+2);
  40. for(ll i=0;i<=n;++i){
  41. sum1[i] = lower_bound(t1+1,t1+n+2,sum1[i]) - t1;
  42. sum2[i] = lower_bound(t2+1,t2+n+2,sum2[i]) - t2;
  43. }
  44. ll m = (n*(n+1))>>1;
  45. ll ans = 0;
  46. //puts("");
  47. add(sum1[0]);
  48. for(ll i=1;i<=n;++i){
  49. ans += i - query(sum1[i]);
  50. add(sum1[i]);
  51. }
  52. memset(C,0,sizeof C);
  53. add(sum2[0]);
  54. for(ll i=1;i<=n;++i){
  55. ans += query(sum2[i] - 1) ;
  56. add(sum2[i]);
  57. }
  58. ans = m - ans;
  59. ll x = gcd(ans,m);
  60. m /= x;ans /= x;
  61. if(ans == 0) printf("0");
  62. else if(m == ans) printf("1");
  63. else printf("%lld/%lld",ans,m);
  64. getchar();getchar();
  65. return 0;
  66. }