fork(6) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define M 1000000007
  4. typedef long long ll;
  5. #define pb push_back
  6. #define F first
  7. #define S second
  8. #define M6 3000009
  9. #define M5 3000009
  10. #define pi 3.14159265
  11. typedef pair<ll,ll> pll;
  12. ll power(ll x,ll n){
  13.     ll ret=1;
  14.     while(n>0){
  15.         if(n&1) ret=(ret*x);
  16.         x=(x*x);
  17.         n/=2;
  18.     }
  19.     return ret;
  20. }
  21. ll m,n,ar[M5],cr[M5],tree[M6],ql[M5],qr[M6];
  22. void update(ll st,ll en,ll nd,ll i,ll v){
  23.     if(st==en) {tree[nd]+=v; return;}
  24.     ll mid=(st+en)/2;
  25.     if(i>=st&&i<=mid){
  26.         update(st,mid,2*nd,i,v);
  27.     }
  28.     else update(mid+1,en,2*nd+1,i,v);
  29.     tree[nd]=tree[2*nd]+tree[2*nd+1];
  30. }
  31. ll query(ll st,ll en,ll nd,ll qs,ll qe){
  32.     if(st>qe||en<qs) return 0;
  33.     if(st>=qs&&en<=qe) return tree[nd];
  34.     ll mid=(st+en)/2;
  35.     ll p=query(st,mid,2*nd,qs,qe);
  36.     ll q=query(mid+1,en,2*nd+1,qs,qe);
  37.     return p+q;
  38. }
  39. int  main()
  40. {   ios_base::sync_with_stdio (0), cin.tie (0);
  41.     ll test=1,t=1,flag,i,j,k,l,a,b,ans=0,p,q;
  42.     cin>>n>>test;
  43.     vector<ll> v;
  44.     for(i=1;i<=n;i++) cin>>ar[i],ar[i]+=ar[i-1],v.pb(ar[i]);
  45.     v.pb(0);
  46.     for(i=1;i<=test;i++){
  47.         cin>>ql[i]>>qr[i];
  48.         for(j=1;j<=n;j++) v.pb(ar[j]-ql[i]),v.pb(ar[j]-qr[i]);
  49.     }
  50.     sort(v.begin(),v.end());
  51.     for(i=1;i<=test;i++){
  52.         q=(ll)v.size();
  53.         j=lower_bound(v.begin(),v.end(),0)-v.begin();
  54.         update(0,q,1,j,1);
  55.         ans=0;
  56.         for(j=1;j<=n;j++){
  57.             a=ar[j]-qr[i]; b=ar[j]-ql[i];
  58.             a=lower_bound(v.begin(),v.end(),a)-v.begin();
  59.             b=lower_bound(v.begin(),v.end(),b)-v.begin();
  60.             ans+=query(0,q,1,a,b);
  61.             k=lower_bound(v.begin(),v.end(),ar[j])-v.begin();
  62.             update(0,q,1,k,1);
  63.         }
  64.         j=lower_bound(v.begin(),v.end(),0)-v.begin();
  65.         update(0,q,1,j,-1);
  66.         for(j=1;j<=n;j++){
  67.             k=lower_bound(v.begin(),v.end(),ar[j])-v.begin();
  68.             update(0,q,1,k,-1);
  69.         }
  70.         cout<<ans<<"\n";
  71.     }
  72.     return 0;
  73. }
Success #stdin #stdout 0s 4352KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/w6W8cG
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

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!