fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n;
  4. int a[1000005];
  5. long long sum[1000005];
  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[i]=sum[i-1]+(a[i]-p);
  42.         v.push_back(sum[i]);
  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.     for(int i=1;i<=n;i++)
  56.     {
  57.         if(sum[i]>=0)
  58.             ans++;
  59.         ans+=sumq(1,0,c-1,0,in[sum[i]]);
  60.         add(1,0,c-1,in[sum[i]]);
  61.     }
  62.     printf("%d\n",ans);
  63.     return 0;
  64. }
Success #stdin #stdout 0s 30768KB
comments (?)
stdin
copy 
3
1 3 2
2
stdout
copy 
5
https://ideone.com/jycaHV
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!