fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long int
  3. #define vec vector<ll>
  4. #define f(var,a,b) for(ll var = a ; var < b ; var++ )
  5. #define fasthoja ios_base::sync_with_stdio(false); cin.tie(NULL);
  6. using namespace std;
  7.  
  8. // This will initialize our diff array
  9. void makeDiff( vec &diff , vec &arr) {
  10. 	f(i,0,arr.size() ) {
  11. 		if( i == 0 ) // first compartment
  12. 			diff[i] = arr[i];
  13. 		else
  14. 			diff[i] = arr[i] - arr[i-1];
  15. 	}
  16. }
  17.  
  18.  
  19. // This will update our difference array in O(1)
  20. void updateDiff( vec &diff ,ll l , ll r , ll x ) {
  21. 	diff[l-1] += x; 
  22. 	diff[r+1-1] -= x;
  23. }
  24.  
  25. // This will just print our diff array by taking prefix-sum of it
  26. void printDiff( vec &diff ) {
  27. 	ll sum = 0;
  28. 	vec fans;
  29. 	f(i,0,diff.size()-1) {
  30. 		sum += diff[i];
  31. 		fans.push_back(sum);
  32. 	}
  33. 	sum = 0;
  34. 	f(i,0,fans.size())  sum += fans[i];
  35. 	cout << sum << "\n";
  36. }
  37.  
  38. int main(void) {
  39.  
  40.     fasthoja;
  41.     ll t; cin >> t;
  42.     while(t-- ){ 
  43.     	ll n; cin >> n;
  44. 	    vec v(n); f(i,0,n) cin >> v[i];
  45.  
  46. 	    vec diff(n+1,0);
  47. 	    makeDiff(diff,v);
  48.  
  49. 	    ll q; cin >> q;
  50. 	    while(q--) {
  51.     		ll l,r,x; cin >> l >> r >> x;
  52.     		updateDiff( diff, l , r, x );
  53. 		}
  54. 		printDiff(diff);
  55. 	} 
  56.  
  57. 	return 0;
  58. }
  59. /*
  60.  
  61. 1
  62. 5
  63. 1 2 3 4 5
  64. 2
  65. 1 3 10
  66. 2 4 15
  67.  
  68. */
Success #stdin #stdout 0s 4400KB
comments (?)
stdin
copy 
1
5
1 2 3 4 5
2
1 3 10
2 4 15
stdout
copy 
90
https://ideone.com/5s19Ts
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!