Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int MAXN = 2000007;
- #define ll long long
- #define pb push_back
- vector <ll> tree(4*MAXN),vec(MAXN, 0),lazy(4*MAXN, -1);
- void clearLazy(ll node, ll b, ll e)
- {
- if (b == e) {if (lazy[node] != -1) vec[b] = lazy[node];}
- else if (lazy[node] != -1)
- {
- ll left = node*2;
- ll right = (2*node)+1;
- lazy[left] = lazy[node];
- lazy[right] = lazy[node];
- }
- lazy[node] = -1;
- }
- void updateRange(ll node, ll b, ll e, ll i, ll j, ll value)
- {
- clearLazy(node, b, e);
- if (j<b || i>e) return;
- if (b>=i && e<=j)
- {
- lazy[node] = value;
- clearLazy(node,b,e);
- return;
- }
- ll left = node*2;
- ll right = (2*node)+1;
- ll mid = (b+e)/2;
- updateRange(left, b, mid, i, j, value);
- updateRange(right, mid+1, e, i, j, value);
- }
- void query(ll node, ll b, ll e, ll ind)
- {
- clearLazy(node, b, e);
- if (b>ind || e<ind) return;
- if (b>=ind && e<=ind)
- {
- clearLazy(node, b, e);
- return;
- }
- ll left = 2*node;
- ll right = (2*node)+1;
- ll mid = (b+e)/2;
- query(left,b,mid,ind);
- query(right,mid+1,e,ind);
- return;
- }
- int main()
- {
- ll n, q;
- cin >> n >> q;
- while (q--)
- {
- ll l, r, value; cin >> l >> r >> value;
- updateRange(1, 1, n, l, r, value);
- }
- for (int i=1;i<=n;i++)
- {
- query(1,1,n,i);
- cout << vec[i] << " ";
- }
- cout<<endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment