fork download 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define pb push_back
  4. #define run_faster ios::sync_with_stdio (false); cin.tie (0); cout.tie (0); ios_base::sync_with_stdio(0); cin.tie(nullptr);
  5. #define F first
  6. #define S second
  7. #define emb emplace_back
  8. #define pii pair<int,int>
  9. using namespace std;
  10.  
  11. const int N = 1e5+9;
  12. int n, q, k;
  13. ll a[N];
  14. ll f1[N], f2[N];
  15.  
  16. void upd( ll f[], int id, ll x ) {
  17. 	for( int i = id; i <= n+1; i |= i+1 ) {
  18. 		f[i] += x;
  19. 	}
  20. }
  21. void range_upd( ll f[], int l, int r, ll x ) {
  22. 	upd(f, l, x);
  23. 	upd(f, r+1, -x);
  24. }
  25. ll pref(ll f[], int r) {
  26. 	ll s = 0;
  27. 	for( int i = r; i >= 0; i = (i&(i+1))-1 ) {
  28. 		s += f[i];
  29. 	}
  30. 	return s;
  31. }
  32.  
  33. int main() {
  34. 	#ifdef MY_COMP
  35. 		freopen("input.txt", "r", stdin);
  36. 		freopen("output.txt", "w", stdout);
  37. 	#endif
  38. 	run_faster;
  39.  
  40. 	cin >> n >> q >> k;
  41. 	for( int i = 1; i <= n; i++ ) {
  42. 		cin >> a[i];
  43. 		range_upd(f1,i,i,a[i]);
  44. 	}
  45. 	int L[q+1], R[q+1]; ll D[q+1];
  46. 	for( int i = 1; i <= q; i++ ) {
  47. 		cin >> L[i] >> R[i] >> D[i];
  48. 	}
  49. 	while( k-- ) {
  50. 		int x, y;
  51. 		cin >> x >> y;
  52. 		range_upd(f2,x,y,1);
  53. 	}
  54. 	for( int i = 1; i <= q; i++ ) {
  55. 		ll cnt = pref(f2,i);
  56. 		range_upd(f1,L[i],R[i],1LL*D[i]*cnt);
  57. 	}
  58. 	for( int i = 1; i <= n; i++ ) {
  59. 		cout << pref(f1,i) << " ";
  60. 	}
  61.  
  62. 	return 0;
  63. }
  64.  
Success #stdin #stdout 0.01s 5472KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/wOUVpx
language:
C++ (gcc 8.3)
created:
228 days 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!