fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #ifdef ONLINE_JUDGE
  5. #define debug(...) 42
  6. #define debugArr(...) 42
  7. #endif
  8.  
  9. #define ll long long 
  10. #define vll vector<ll>
  11. #define loop(i, c, n) for(ll i = c; i < n; ++i)
  12. #define feach(x, a) for(auto& x : a)
  13. #define endl "\n"
  14. #define pb push_back
  15. #define all(x) x.begin(), x.end()
  16.  
  17. /*
  18. Queries act on operations, and operations act on the array
  19. so use a difference array once at each layer
  20. */
  21.  
  22. void solve(){
  23.     ll n, m, k; cin >> n >> m >> k;
  24.     vll a(n); feach(x, a) cin >> x;
  25.     vector<array<ll, 3>> ops(m);
  26.     loop(i, 0, m){
  27.         cin >> ops[i][0] >> ops[i][1] >> ops[i][2];
  28.         --ops[i][0], --ops[i][1];
  29.     }
  30.  
  31.     // this gives me the count of each operations at the end
  32.     vll cntops(m + 1, 0);
  33.  
  34.     loop(i, 0, k){
  35.         ll x, y; cin >> x >> y; --x, --y;
  36.  
  37.         // a query i applies operations [x_i, y_i] on the array
  38.         // thus, each operation get incremented by 1 in count for
  39.         // each query
  40.  
  41.         // so we get +1 incremented in [x_i, y_i]
  42.  
  43.         // apply diff array technique on this
  44.         cntops[x]++;
  45.         cntops[y + 1]--;
  46.     }
  47.     partial_sum(all(cntops), cntops.begin()); // prefix sum
  48.     debug(cntops);
  49.  
  50.     // this is the diff array to find the final diff being applied 
  51.     // to my original array
  52.     vll diff(n + 1, 0); 
  53.  
  54.     loop(i, 0, m){
  55.  
  56.         // an operation i increments [l_i,r_i] by op[i][2] or d_i, 
  57.         // and we have cntops[i] number of operations of ith operation 
  58.         // after processing k queries
  59.  
  60.         // so we get op[i][2] * cntops[i] incremented in [l_i, r_i]
  61.  
  62.         // apply diff array technique on this
  63.         diff[ops[i][0]] += cntops[i] * ops[i][2]; 
  64.         diff[ops[i][1] + 1] -= cntops[i] * ops[i][2];
  65.     }
  66.     partial_sum(all(diff), diff.begin());
  67.     debug(diff);
  68.     vll res(n, 0);
  69.     loop(i, 0, n){
  70.         res[i] = diff[i] + a[i];
  71.     }
  72.     loop(i, 0, n){
  73.         cout << res[i] << " \n"[i == n - 1];
  74.     }
  75. }
  76.  
  77. int32_t main(){
  78.     ios_base::sync_with_stdio(0); cin.tie(0);
  79.     int tc = 1; // cin >> tc;
  80.     while(tc--) solve();
  81.     return 0;
  82. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
3 3 3
1 2 3
1 2 1
1 3 2
2 3 4
1 2
1 3
2 3
stdout
copy 
9 18 17
https://ideone.com/8B5rW2
language:
C++14 (gcc 8.3)
created:
2 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!