fork(1) download
copy 
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. long long int sums[524300];
  4. long long int update[524300];
  5. long int v;
  6. long long int query(long int i,long int l,long int r,long int p,long int q)
  7. {
  8.     // printf("here %d %d %d %d\n",p,q,l,r);
  9.      if(p>q)
  10.      return 0;
  11.       sums[i]+=update[i]*(r-l+1);
  12.        update[i*2]+=update[i];
  13.        update[i*2+1]+=update[i];
  14.        update[i]=0;
  15.  
  16.      if(l==p && q==r)
  17.       return sums[i];
  18.  
  19.  
  20.      long int m = (l+r)/2;
  21.      long long int s;
  22.  
  23.      if(q<=m)
  24.      return query(i*2,l,m,p,q);
  25.  
  26.      if(m+1<=p)
  27.      return query(i*2+1,m+1,r,p,q);
  28.  
  29.      s=query(i*2,l,m,p,m);
  30.      s+=query(i*2+1,m+1,r,m+1,q);
  31.      return s;
  32. }
  33. void add(long int i,long int l,long int r,long int p,long int q)
  34. {
  35.  
  36.      if(p>q)
  37.      return;
  38.  
  39.      long int m=(l+r)/2;
  40.  
  41.      sums[i]+=(q-p+1)*v;
  42.      if(l==p && r==q)
  43.      { update[i*2]+=v;
  44.        update[i*2+1]+=v;
  45.        return;
  46.      }
  47.  
  48.      if(q<=m)
  49.      { add(i*2,l,m,p,q);
  50.        return;
  51.      }
  52.      if(m+1<=p)
  53.      { add(i*2+1,m+1,r,p,q);
  54.        return;
  55.      }
  56.  
  57.        add(i*2,l,m,p,m);
  58.        add(i*2+1,m+1,r,m+1,q);
  59.        return;
  60. }
  61. int main(void)
  62. {
  63.     int t,b;
  64.     long int n,c,p,q;
  65.     scanf("%d",&t);
  66.     while(t--)
  67.     {
  68.        scanf("%ld",&n);
  69.        scanf("%ld",&c);
  70.        memset(sums,0,sizeof(long long int)*524300);
  71.        memset(update,0,sizeof(long long int)*524300);
  72.        while(c--)
  73.        {  scanf("%d %ld %ld",&b,&p,&q);
  74.           if(b==1)
  75.           { printf("%lld\n",query(1,0,n-1,p-1,q-1));}
  76.           else
  77.           { scanf("%ld",&v);
  78.             add(1,0,n-1,p-1,q-1);
  79.           }
  80.        }
  81.     }
  82.     //scanf("%d",&v);
  83.     return 0;
  84. }
  85.  
  86.  
  87.  
  88.  
Time limit exceeded #stdin #stdout 5s 10024KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/NhDuYo
language:
C (gcc 8.3)
created:
12 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!