fork download
copy 
  1. /*
  2. Author : Chandan Agrawal
  3. College : Poornima College of Engg. jaipur, Raj
  4. Mail : chandanagrawal23@gmail.com
  5. " when you are not practicing someone else is ,
  6.  and the day u meet them u will lose "
  7. */
  8. #include<bits/stdc++.h>
  9. #include<stdio.h>
  10. using namespace std;
  11.  
  12. #define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  13. #define MAX 100050
  14.  
  15. #define ll long long
  16. #define ld long double
  17. #define lli long long int
  18.  
  19. #define pb push_back
  20. #define INF 1000000000000
  21. #define mod 1000000007
  22.  
  23. // trignometric function always give value in Radians only
  24. #define PI acos(-1) //3.1415926535897932384626433832795028
  25. #define dsin(degree) sin(degree*(PI/180.0))
  26. #define dcos(degree) cos(degree*(PI/180.0))
  27. #define dtan(degree) tan(degree*(PI/180.0))
  28.  
  29. #define rsin(radian) sin(radian)
  30. #define rcos(radian) cos(radian)
  31. #define rtan(radian) tan(radian)
  32.  
  33. #define mem0(a) memset(a,0,sizeof(a))
  34. #define mem1(a) memset(a,-1,sizeof(a))
  35. #define memf(a) memset(a,false,sizeof(a))
  36.  
  37. #define loop(i,n)  for (lli i = 0; i < n; i++)
  38. #define FOR(i,a,b) for (lli i = a; i < b; i++)
  39.  
  40. #define all(v) v.begin(),v.end()
  41. #define rall(v) v.rbegin(),v.rend()
  42. #define makeuniq(v) v.resize(unique(all(v)) - v.begin()); //only uniq element in vector after this
  43. #define sz(x) int(x.size())
  44. #define F first
  45. #define S second
  46.  
  47. #define mii map<lli,lli>
  48.  
  49. #define pii pair<lli,lli>
  50.  
  51. #define vi vector<lli>
  52. #define vvi vector<vi>
  53. #define vpi vector<pii>
  54. #define vbool vector<bool>
  55.  
  56. #define seti set<lli>
  57.  
  58. #define gcd(a,b) __gcd((a),(b))
  59. #define lcm(a,b) (a/gcd(a,b))*b
  60. #define abs(x) ((x < 0)?-(x):x)
  61.  
  62. #define endl '\n'
  63.  
  64. template <typename Head>
  65. void print(Head&& head)
  66. {
  67.     cout<<head<<endl;
  68. }
  69. template <typename Head, typename... Tail>
  70. void print(Head&& head, Tail... tail)
  71. {
  72.     cout<<head<<" ";
  73.     print(tail...);
  74. }
  75.  
  76. #define scanarr(a,n) for(lli i=0;i<n;i++)    cin>>a[i];
  77. #define scanvec(a,n) for(lli i=0;i<n;i++){ lli x ; cin>>x; a.pb(x);}
  78.  
  79. #define printarr(a,n) for(lli i=0;i<n;i++)   cout<<a[i]<<" "; cout<<endl;
  80. #define printvec(vec) for(auto xt : vec) cout<<xt<<" ";    cout<<"\n";
  81.  
  82. #define FD(N) fixed<<setprecision(N)
  83.  
  84. #define deb(x) cout<<#x<<" "<<x<<endl;
  85.  
  86. /*
  87. 1D vector -  vi dp(n,value);
  88. 2D vector -  vvi dp(n,vi(n,value));
  89. */
  90.  
  91. // chandan1,2
  92. void chandan1(){int y=1;return;}
  93. void chandan2(){
  94.         loop(i,10){
  95.         lli x=1;
  96.     }
  97.     return(chandan1());
  98. }
  99.  
  100. //---------------------------------------------------SQRT_DECOMPO-------------------------------------------------------
  101.  
  102. lli n , a[MAX];
  103. lli block[400];
  104. lli lazy[400];
  105. lli blk_sz;
  106.  
  107. // clear all data
  108. void clear()
  109. {
  110.     mem0(a);
  111.     mem0(block);
  112.     mem0(lazy);
  113. }
  114.  
  115. // preprocess array to sqrt decomposition
  116. void preprocess(lli n)
  117. {
  118.     blk_sz = sqrt(n);
  119.  
  120.     lli blk_ind = -1;
  121.  
  122.     loop(i,n)
  123.     {
  124.         if(i % blk_sz == 0)
  125.             blk_ind++;
  126.  
  127.         block[blk_ind]+=(a[i]);
  128.     }
  129. }
  130.  
  131. // query to find min from l to r in range
  132. lli query(lli l , lli r)
  133. {
  134.     lli left_block = l/blk_sz;
  135.  
  136.     lli right_block = r/blk_sz;
  137.  
  138.     lli sum = 0;
  139.  
  140.     if(left_block == right_block)
  141.     {
  142.         for(lli i=l;i<=r;i++)
  143.             sum += (a[i] + lazy[i/blk_sz]);
  144.     }
  145.     else
  146.     {
  147.         for(lli i=l;i<blk_sz*(left_block+1);i++) // traversing first block in range 
  148.         {
  149.             sum += (a[i] + lazy[i/blk_sz]);
  150.         }   
  151.         for(lli i=left_block+1;i<right_block;i++) // traversing completely overlapped blocks in range 
  152.         {
  153.             sum += block[i] + lazy[i]*(blk_sz);
  154.         }
  155.  
  156.         for(lli i=blk_sz*right_block; i<=r; i++) // traversing last block in range 
  157.         {
  158.             sum += (a[i] + lazy[i/blk_sz]);
  159.         }
  160.     }
  161.  
  162.     return sum;
  163. }
  164.  
  165. void update(lli l , lli r , lli val)
  166. {
  167.     lli left_block = l / blk_sz; 
  168.  
  169.     lli right_block = r / blk_sz;
  170.  
  171.     if(left_block == right_block)
  172.     {
  173.         for(lli i=l;i<=r;i++)
  174.             a[i] += val;
  175.     }
  176.     else
  177.     {
  178.         for(lli i=l;i<blk_sz*(left_block+1);i++) // traversing first block in range 
  179.             a[i] += val;
  180.  
  181.         for(lli i=left_block+1;i<right_block;i++) // traversing completely overlapped blocks in range 
  182.             lazy[i] += val;
  183.  
  184.         for(lli i=blk_sz*right_block;i<=r;i++) //// traversing last block in range 
  185.             a[i] += val;
  186.     }
  187. }
  188.  
  189. //---------------------------------------------------SQRT_DECOMPO-------------------------------------------------------
  190.  
  191. int main(){
  192. fastio
  193. chandan2();
  194. lli t;
  195. cin>>t;
  196. while(t--)
  197. {
  198.     lli q;
  199.     cin>>n>>q;
  200.     loop(i,n)
  201.         a[i]=0;
  202.  
  203.     preprocess(n);
  204.  
  205.     while(q--)
  206.     {
  207.         lli type;
  208.         cin>>type;
  209.         if(type == 1)
  210.         {
  211.             lli l,r;
  212.             cin>>l>>r;
  213.             l--;
  214.             r--;
  215.             print(query(l,r));
  216.         }
  217.         else
  218.         {
  219.             lli l,r,val;
  220.             cin>>l>>r>>val;
  221.             --l , --r;
  222.             update(l,r,val);
  223.         }
  224.     }
  225.  
  226.     clear();
  227.  
  228. }
  229.  
  230. return 0;
  231. }
  232. /*
  233. Actual Output -
  234.  
  235. 80
  236. 508
  237.  
  238. My output
  239.  
  240. 80
  241. 460
  242.  
  243. */
Success #stdin #stdout 0s 4376KB
comments (?)
stdin
copy 
1
8 6
0 2 4 26
0 4 8 80
0 4 5 20
1 8 8 
0 5 7 14
1 4 8
stdout
copy 
80
460
https://ideone.com/kCbylL
language:
C++14 (gcc 8.3)
created:
3 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!