hkshakib

Untitled

Feb 6th, 2020
170
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.52 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int MAXN = 2000007;
  4. #define ll long long
  5. #define pb push_back
  6. vector <ll> tree(4*MAXN),vec(MAXN, 0),lazy(4*MAXN, -1);
  7. void clearLazy(ll node, ll b, ll e)
  8. {
  9. if (b == e) {if (lazy[node] != -1) vec[b] = lazy[node];}
  10. else if (lazy[node] != -1)
  11. {
  12. ll left = node*2;
  13. ll right = (2*node)+1;
  14. lazy[left] = lazy[node];
  15. lazy[right] = lazy[node];
  16. }
  17. lazy[node] = -1;
  18. }
  19.  
  20. void updateRange(ll node, ll b, ll e, ll i, ll j, ll value)
  21. {
  22. clearLazy(node, b, e);
  23. if (j<b || i>e) return;
  24. if (b>=i && e<=j)
  25. {
  26. lazy[node] = value;
  27. clearLazy(node,b,e);
  28. return;
  29. }
  30.  
  31. ll left = node*2;
  32. ll right = (2*node)+1;
  33. ll mid = (b+e)/2;
  34.  
  35. updateRange(left, b, mid, i, j, value);
  36. updateRange(right, mid+1, e, i, j, value);
  37. }
  38.  
  39. void query(ll node, ll b, ll e, ll ind)
  40. {
  41. clearLazy(node, b, e);
  42. if (b>ind || e<ind) return;
  43. if (b>=ind && e<=ind)
  44. {
  45. clearLazy(node, b, e);
  46. return;
  47. }
  48.  
  49. ll left = 2*node;
  50. ll right = (2*node)+1;
  51. ll mid = (b+e)/2;
  52.  
  53. query(left,b,mid,ind);
  54. query(right,mid+1,e,ind);
  55. return;
  56. }
  57. int main()
  58. {
  59. ll n, q;
  60. cin >> n >> q;
  61. while (q--)
  62. {
  63. ll l, r, value; cin >> l >> r >> value;
  64. updateRange(1, 1, n, l, r, value);
  65. }
  66.  
  67. for (int i=1;i<=n;i++)
  68. {
  69. query(1,1,n,i);
  70. cout << vec[i] << " ";
  71. }
  72. cout<<endl;
  73. }
Advertisement
Add Comment
Please, Sign In to add comment