fork download
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n;
  4. int a[1000005];
  5. long long sum=0;
  6. long long p;
  7. int ans=0;
  8. map<long long,int>in;
  9. vector<long long>v;
  10. int st[4000006];
  11. int left(int p){return (p<<1);}
  12. int right(int p){return (p<<1)+1;}
  13. void add(int p,int l,int r,int x)
  14. {
  15. if(l>x||r<x)return;
  16. if(l==r)
  17. {
  18. if(l==x)
  19. {
  20. st[p]++;
  21. }
  22. return;
  23. }
  24. add(left(p),l,(l+r)/2,x);
  25. add(right(p),((l+r)/2)+1,r,x);
  26. st[p]=st[left(p)]+st[right(p)];
  27. }
  28. int sumq(int p,int l,int r,int i,int j)
  29. {
  30. if(r<i||l>j)return 0;
  31. if(l>=i&&r<=j)return st[p];
  32. return sumq(left(p),l,(l+r)/2,i,j)+sumq(right(p),((l+r)/2)+1,r,i,j);
  33. }
  34. int main()
  35. {
  36. scanf("%d",&n);
  37. for(int i=1;i<=n;i++)
  38. scanf("%d",&a[i]);
  39. scanf("%d",&p);
  40. for(int i=1;i<=n;i++){
  41. sum=sum+(a[i]-p);
  42. v.push_back(sum);
  43. }
  44. sort(v.begin(),v.end());
  45. in[v[0]]=0;
  46. int c=1;
  47. for(int i=1;i<v.size();i++)
  48. {
  49. if(v[i]!=v[i-1])
  50. {
  51. in[v[i]]=c;
  52. c++;
  53. }
  54. }
  55. sum=0;
  56. for(int i=1;i<=n;i++)
  57. {
  58. sum=sum+(a[i]-p);
  59. if(sum>=0)
  60. ans++;
  61. ans+=sumq(1,0,c-1,0,in[sum]);
  62. add(1,0,c-1,in[sum]);
  63. }
  64. printf("%d\n",ans);
  65. return 0;
  66. }
Runtime error #stdin #stdout 0s 22944KB
stdin
Standard input is empty
stdout
Standard output is empty