fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define FOR(_i,_a,_b) for(int _i=_a;_i<=_b;_i++)
  5. #define TCASE int _t;cin>>_t;FOR(_i,1,_t)
  6. #define NFOR(_i,_a,_b) for(int _i=_a;_i>=_b;_i--)
  7. #define pb push_back
  8. #define all(_vec) _vec.begin(),_vec.end()
  9. #define rall(_vec) _vec.rbegin(),_vec.rend()
  10. #define READ(x) freopen(x,"r",stdin);
  11. #define VECTORPRINT(_vec) {int _t=0;while(_t<_vec.size()){cout<<_vec[_t++]<<' ';}}
  12. #define whatis(x) cout<<#x<<"= "<<x<<endl;
  13. #define REP(i, n) for(int i=0;i<n;i++)
  14. #define ARR_SIZE(_arr) sizeof(_arr)/sizeof(_arr[0])
  15. #define bit(x,i) (x&(1<<i))  //select the bit of position i of x
  16. #define bitcount(x) __builtin_popcount(x);
  17. #define boost ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  18. #define most_significant(x) __builtin_clzll (unsigned long long)
  19. #define maxx(a,b) (a>b?a:b)
  20. #define getx getchar_unlocked
  21. #define putx putchar_unlocked
  22.  
  23. typedef vector<int> vi;
  24. typedef vector<vi > vvi;
  25. typedef vector<pair<int,int> > vpii;
  26. typedef long long lli;
  27. typedef unsigned long long ulli;
  28. typedef vector<lli> vlli;
  29. typedef vector<vector<lli> > matrix;
  30. typedef vector<double> vd;
  31. typedef vector<long double> vld;
  32.  
  33. int n;
  34. int rootn,sz;
  35. vlli arr;
  36. vlli bsum;
  37. vlli bchange;
  38.  
  39. void update(){
  40.     lli x,y,k;
  41.     cin>>x>>y>>k; x--; y--;
  42.     int c_l=x/rootn,  c_r=y/rootn;
  43.     if(c_l==c_r){
  44.         for(int i=x ; i<=y ; i++)
  45.             arr[i]+=k;
  46.         bsum[c_l]+=(y-x+1)*k;
  47.     }
  48.     else{
  49.         for(int i=x ; i<=(c_l+1)*rootn-1 && i<=sz-1 ; i++)
  50.             arr[i]+=k;
  51.         bsum[c_l]+=((c_l+1)*rootn-1-x+1)*k;
  52.  
  53.         for(int i=c_l+1 ; i<=c_r-1 && i<=sz-1; i++){
  54.             bsum[i]+=(lli)rootn*k;
  55.             bchange[i]+= k;
  56.         }
  57.  
  58.         for(int i=c_r*rootn ; i<=y && i<sz-1; i++)
  59.              arr[i]+=k;
  60.         bsum[c_r]+=(y-c_r*rootn+1)*k;
  61.     }
  62. }
  63.  
  64. lli getsum(int y){
  65.     int x=0;
  66.     int c_l=0,  c_r=y/rootn;
  67.     lli sum=0;
  68.     if(c_l==c_r)
  69.         for(int i=x ; i<=y ; i++)
  70.             sum+=arr[i]+bchange[c_l];
  71.     else{
  72.         for(int i=x ; i<=(c_l+1)*rootn-1 ; i++)
  73.             sum+=arr[i]+bchange[c_l];
  74.         for(int i=c_l+1 ; i<=c_r-1 ; i++)
  75.             sum+=bsum[i];
  76.         for(int i=c_r*rootn ; i<=y ; i++)
  77.             sum+=arr[i]+bchange[c_r];
  78.     }
  79.     return sum;
  80. }
  81.  
  82. void printsum(){
  83.     int x,y;
  84.     cin>>x>>y; x--; y--;
  85.     lli maxsum=LLONG_MIN;
  86.     lli tmpsum;
  87.     FOR(i,x,y){
  88.         tmpsum=getsum(i);
  89.         maxsum=maxx(maxsum,tmpsum);
  90.     }
  91.     cout<<maxsum<<endl;
  92. }
  93.  
  94. void initialise(){
  95.     for(int i=0;i<=n-1;i+=rootn)
  96.         for(int j=i;j<=i+rootn-1;j++)
  97.             if(j<=n-1)
  98.                 bsum[(int)i/rootn]+=arr[j];
  99. }
  100.  
  101. int main(){
  102.     boost
  103.     //freopen("in.txt","r",stdin);
  104.     cin>>n;
  105.     arr.resize(n);
  106.     FOR(i,0,n-1) cin>>arr[i];
  107.     rootn=floor(sqrt(n));
  108.     sz=ceil(sqrt(n));
  109.     bsum.resize(sz);
  110.     bchange.resize(sz);
  111.  
  112.     initialise();
  113.  
  114.     int queries,tmp;
  115.     cin>>queries;
  116.     while(queries--){
  117.         cin>>tmp;
  118.         if(tmp==0) update();
  119.         else printsum();
  120.     }
  121.  
  122.     return 0;
  123. }
  124.  
Success #stdin #stdout 0s 3456KB
comments (?)
stdin
copy 
5
238 -9622 5181 202 -6943
5
1 3 4
0 5 5 4846
1 3 5
0 3 5 -7471
1 3 3
stdout
copy 
-4001
-4001
-11674
https://ideone.com/jePYPu
language:
C++ (gcc 8.3)
created:
7 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!