Problem Link:
Author: Chaitanya Hardikar
Tester: Pankaj Goyal
Editorialist: Chaitanya Hardikar
Difficulty
MEDIUM
PREREQUISITES
Segment Trees, Lazy Propagation
APPROACH
First, we will set all values of array to the maximum value possible (2 31 -1).
Consider an index, if that index isn’t part of any range, we keep that array value
as the maximum. Now suppose some index is included in multiple ranges, then
the maximum value of this array element will be the bitwise ‘AND’ value of all
intersecting range ‘OR’ values. Hence, we will build a segment tree that will
calculate the ‘AND’ value and use lazy propagation to update ranges for the m
queries given.
After setting each value of array to the optimal(maximum) value possible as
described above, we need to check whether the given m conditions are satisfied
or not. For this, we can build another segment tree to calculate the ‘OR’ value of
ranges and verify whether all m conditions are satisfied. If all m conditions are
satisfied we print the array, else we will output “-1”.
Time Complexity-O( (n+m)*log(n) )
Space complexity-O(n+m)
SETTER’S SOLUTION:
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define nl cout << "\n"
#define pb push_back
#define loopf(i,a,b) for(int i=a;i<b;i++)
typedef vector<ll> vll;
#define read(v) for(int i=0;i<(int)v.size();++i) cin>>v[i]
#define print(v) {for(int i=0;i<(int)v.size();++i)cout<<v[i]<<" ";nl;}
const ll inf = INT_MAX; // = 2^31 - 1(max array value)
vll st, arr, lazy;
ll merge(ll n1, ll n2){
return (n1&n2);
}
ll buildST(ll ss, ll se, ll si){
if(ss==se){
return st[si] = arr[ss];
}
ll mid=(ss+se)/2;
ll n1 = buildST(ss,mid,2*si+1);
ll n2 = buildST(mid+1,se,2*si+2);
return st[si] = merge(n1,n2);
}
ll query(ll ss, ll se, ll si, ll l, ll r){
if(lazy[si]!=inf){
st[si]&=lazy[si];
if(ss!=se){
lazy[2*si+1]&=lazy[si];
lazy[2*si+2]&=lazy[si];
}
lazy[si]=inf;
}
if(ss>r || se<l) return inf;
if(ss>=l && se<=r)return st[si];
ll mid=(ss+se)/2;
return merge(query(ss,mid,2*si+1,l,r) , query(mid+1,se,2*si+2,l,r));
}
void updateRange(ll ss, ll se, ll si, ll l, ll r, ll val){
if(lazy[si]!=inf){
st[si]&=lazy[si];
if(ss!=se){
lazy[2*si+1]&=lazy[si];
lazy[2*si+2]&=lazy[si];
}
lazy[si]=inf;
}
if(ss>se || r<ss || l>se) return;
if(ss>=l && se<=r){
st[si]&=val;
if(ss!=se){
lazy[2*si+1]&=val;
lazy[2*si+2]&=val;
}
return;
}
ll mid=(ss+se)/2;
updateRange(ss,mid,2*si+1,l,r,val);
updateRange(mid+1,se,2*si+2,l,r,val);
st[si] = merge(st[2*si+1], st[2*si+2]);
}
vll st2;
ll buildOR(ll ss, ll se, ll si){
if(ss==se){
return st2[si] = arr[ss];
}
ll mid=(ss+se)/2;
ll n1 = buildOR(ss,mid,2*si+1);
ll n2 = buildOR(mid+1,se,2*si+2);
return st2[si] = (n1|n2);
}
ll getOr(ll ss, ll se, ll si, ll l, ll r){
if(ss>=l && se<=r)return st2[si];
if(ss>r || se<l || ss>se) return 0;
ll mid=(ss+se)/2;
ll n1 = getOr(ss,mid,2*si+1,l,r);
ll n2 = getOr(mid+1,se,2*si+2,l,r);
return (n1|n2);
}
void solve();
int main() {
cin.tie(NULL);
cout.tie(NULL);
ios_base::sync_with_stdio(false);
int t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}
void solve(){
ll n,m; cin>>n>>m;
arr.resize(n,inf); st.resize(4*n); st2.resize(4*n); lazy.resize(4*n,inf);
buildST(0,n-1,0);
vll l(m),r(m),val(m);
loopf(i,0,m){
cin>>l[i]>>r[i]>>val[i];
l[i]--, r[i]--;
updateRange(0,n-1,0,l[i],r[i],val[i]);
}
loopf(i,0,n)arr[i] = query(0,n-1,0,i,i);
// Is Data Consistent? : Check
buildOR(0,n-1,0);
loopf(i,0,m){
if(getOr(0,n-1,0,l[i],r[i])!=val[i]){
arr.clear(); st.clear(); lazy.clear(); st2.clear();
cout<<"-1\n"; return;
}
}
print(arr);
arr.clear(); st.clear(); lazy.clear(); st2.clear();
}