fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
  4. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  5. int rnd(int l,int r){return l+rng()%(r-l+1);}
  6. #define fasty ios_base::sync_with_stdio(0),cin.tie(0);
  7. #define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
  8. #define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a)
  9. #define forv(a,b) for(auto&a:b)
  10. #define fi first
  11. #define se second
  12. #define pb push_back
  13. #define ii pair<int,int>
  14. #define mt make_tuple
  15. #define all(a) a.begin(),a.end()
  16. #define reset(f, x) memset(f, x, sizeof(f))
  17. #define bit(x,i) ((x>>(i-1))&1)
  18. #define on(x,i) (x|(1ll<<(i-1)))
  19. #define off(x,i) (x&~(1<<(i-1)))
  20. #define gg exit(0);
  21.  
  22. const int N=500010;
  23.  
  24. int n,m;
  25. int a[N],b[N];
  26. long long sa[N],sb[N];
  27.  
  28. struct pack{
  29.     long long x,y;
  30.     int qn;
  31. };
  32.  
  33. struct fenwick{
  34.     long long tot=0;
  35.     vector<long long> val;
  36.     vector<pair<long long,long long>> pf;
  37.     vector<pack> bit;
  38.     void add(long long i,long long j){
  39.         val.pb(i-j);
  40.         pf.pb({i,j});
  41.         tot+=j;
  42.     }
  43.     void upd(long long i,long long x,long long y){
  44.         i=lower_bound(all(val),i)-val.begin()+1;
  45.         for(;i;i-=i&-i){
  46.             bit[i].x+=x;
  47.             bit[i].y+=y;
  48.             bit[i].qn+=1;
  49.         }
  50.     }
  51.     pack que(long long i){
  52.         i=lower_bound(all(val),i)-val.begin()+1;
  53.         long long x=0,y=0; int qn=0;
  54.         for(;i<=val.size();i+=i&-i){
  55.             x+=bit[i].x;
  56.             y+=bit[i].y;
  57.             qn+=bit[i].qn;
  58.         }
  59.         return {x,y,qn};
  60.     }
  61.     void build(){
  62.         sort(all(val)); val.erase(unique(all(val)),val.end());
  63.         bit.resize(val.size()+1);
  64.         forv(i,pf) upd(i.fi-i.se,i.fi,i.se);
  65.     }
  66. }T[N*4];
  67.  
  68. void dfs1(int s,int l,int r){
  69.     if(l<r){
  70.         int m=(l+r)/2;
  71.         dfs1(2*s,l,m); dfs1(2*s+1,m+1,r);
  72.     }
  73.     forinc(i,l,r) T[s].add(sa[i]-sa[l-1],sb[i]-sb[l-1]);
  74.     T[s].build();
  75. }
  76.  
  77. long long pa,pb,ret;
  78.  
  79. void dfs2(int s,int l,int r,int u,int v){
  80.     if(l>v||u>r) return;
  81.     if(u<=l&&r<=v){
  82.         long long diff=pa-pb;
  83.         pack i=T[s].que(-diff);
  84.         ret+=i.x + pa * i.qn;
  85.         ret+=T[s].tot-i.y + pb * (r-l+1-i.qn);
  86.         pa+=sa[r]-sa[l-1];
  87.         pb+=sb[r]-sb[l-1];
  88.         return;
  89.     }
  90.     int m=(l+r)/2;
  91.     dfs2(2*s,l,m,u,v); dfs2(2*s+1,m+1,r,u,v);
  92. }
  93.  
  94. main(){
  95.     #define task "TASK"
  96.     //freopen(task".inp","r",stdin);
  97.     //freopen(task".out","w",stdout);
  98.  
  99.     n=in,m=in;
  100.     forinc(i,1,n) sa[i]=sa[i-1]+(a[i]=in);
  101.     forinc(i,1,n) sb[i]=sb[i-1]+(b[i]=in);
  102.  
  103.     dfs1(1,1,n);
  104.     forinc(i,1,m){
  105.         int l=in,r=in; pa=pb=ret=0;
  106.         dfs2(1,1,n,l,r);
  107.         cout<<ret<<"\n";
  108.     }
  109. }
Time limit exceeded #stdin #stdout 5s 159476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/xqUAb2
language:
C++ (gcc 8.3)
created:
4 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!