#include "wall.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define setp(x) cout<<fixed<<setprecision(x)
#define forn(i,a,b) for(int i=(a);i<(b);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define F first
#define S second
#define pqueue priority_queue
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
void amin(ll &a, ll b){ a=min(a,b); }
void amax(ll &a, ll b){ a=max(a,b); }
void YES(){cout<<"YES\n";} void NO(){cout<<"NO\n";}
void SD(int t=0){ cout<<"PASSED "<<t<<endl; }
const ll INF = ll(1e9);
const int MOD = 998244353;
bool DEBUG = 1;
const int MAXN = 2000005;
struct Node {
int mn = 0, mx = INF;
};
class LazySegmentTree {
private:
vector<Node> v, lazy;
int size_;
void update(int s, int e, const Node &val, int k, int l, int r)
{
push(k, l, r);
if(r < s || e < l) return;
if(s <= l && r <= e){
lazy[k] = val;
push(k, l, r);
return;
}
int mid = (l+r)>>1;
update(s, e, val, 2*k, l, mid);
update(s, e, val, 2*k+1, mid+1, r);
}
Node query(int s, int e, int k, int l, int r)
{
push(k, l, r);
if(r < s || e < l) return Node{-1,INF}; //dummy value
if(s <= l && r <= e) return v[k];
int mid = (l+r)/2;
Node lc = query(s, e, 2*k, l, mid);
Node rc = query(s, e, 2*k+1, mid+1, r);
return merge(lc, rc);
}
public:
LazySegmentTree(): v(vector<Node>()), lazy(vector<Node>()){}
LazySegmentTree(int n_){
for(size_=1;size_<n_;) size_<<=1;
v.resize(4*size_, Node{0,INF});
lazy.resize(4*size_, Node{-1,INF});
}
void push(int k, int l, int r){
if(lazy[k].mn != -1 || lazy[k].mx != INF){
if(lazy[k].mn != -1){
amax(v[k].mn, lazy[k].mn);
amax(v[k].mx, lazy[k].mn);
}
if(lazy[k].mx != INF)
{
amin(v[k].mn, lazy[k].mx);
amin(v[k].mx, lazy[k].mx);
}
if(l != r){
mergelazy(lazy[k*2], lazy[k]);
mergelazy(lazy[k*2+1], lazy[k]);
}
lazy[k] = Node{-1,INF};
}
}
inline Node merge(const Node &a, const Node &b){
return Node{(a.mn != -1 ? a.mn : b.mn), (a.mx != INF ? a.mx : b.mx)};
}
inline void mergelazy(Node &a, const Node &b){
amax(a.mn, b.mn);
amax(a.mx, b.mn);
amin(a.mn, b.mx);
amin(a.mx, b.mx);
}
inline void update(int s, int e, const Node &val){
update(s, e, val, 1, 0, size_-1);
}
inline Node query(int s, int e){
return query(s, e, 1, 0, size_-1);
}
};
void buildWall(int n, int K, int op[], int L[], int R[], int H[], int ans[])
{
LazySegmentTree st(n);
for(int i=0;i<K;i++)
{
if(op[i]==1) st.update(L[i],R[i],Node{H[i],INF});
else st.update(L[i],R[i],Node{-1,H[i]});
}
forn(i,0,n) ans[i] = st.query(i,i).mn;
}
Compilation message
wall.cpp: In member function 'void LazySegmentTree::push(int, int, int)':
wall.cpp:82:15: error: cannot bind non-const lvalue reference of type 'll& {aka long long int&}' to an rvalue of type 'll {aka long long int}'
amax(v[k].mn, lazy[k].mn);
wall.cpp:26:6: note: initializing argument 1 of 'void amax(ll&, ll)'
void amax(ll &a, ll b){ a=max(a,b); }
^~~~
wall.cpp:83:15: error: cannot bind non-const lvalue reference of type 'll& {aka long long int&}' to an rvalue of type 'll {aka long long int}'
amax(v[k].mx, lazy[k].mn);
wall.cpp:26:6: note: initializing argument 1 of 'void amax(ll&, ll)'
void amax(ll &a, ll b){ a=max(a,b); }
^~~~
wall.cpp:87:15: error: cannot bind non-const lvalue reference of type 'll& {aka long long int&}' to an rvalue of type 'll {aka long long int}'
amin(v[k].mn, lazy[k].mx);
wall.cpp:25:6: note: initializing argument 1 of 'void amin(ll&, ll)'
void amin(ll &a, ll b){ a=min(a,b); }
^~~~
wall.cpp:88:15: error: cannot bind non-const lvalue reference of type 'll& {aka long long int&}' to an rvalue of type 'll {aka long long int}'
amin(v[k].mx, lazy[k].mx);
wall.cpp:25:6: note: initializing argument 1 of 'void amin(ll&, ll)'
void amin(ll &a, ll b){ a=min(a,b); }
^~~~
wall.cpp: In member function 'void LazySegmentTree::mergelazy(Node&, const Node&)':
wall.cpp:104:10: error: cannot bind non-const lvalue reference of type 'll& {aka long long int&}' to an rvalue of type 'll {aka long long int}'
amax(a.mn, b.mn);
~~^~
wall.cpp:26:6: note: initializing argument 1 of 'void amax(ll&, ll)'
void amax(ll &a, ll b){ a=max(a,b); }
^~~~
wall.cpp:105:10: error: cannot bind non-const lvalue reference of type 'll& {aka long long int&}' to an rvalue of type 'll {aka long long int}'
amax(a.mx, b.mn);
~~^~
wall.cpp:26:6: note: initializing argument 1 of 'void amax(ll&, ll)'
void amax(ll &a, ll b){ a=max(a,b); }
^~~~
wall.cpp:106:10: error: cannot bind non-const lvalue reference of type 'll& {aka long long int&}' to an rvalue of type 'll {aka long long int}'
amin(a.mn, b.mx);
~~^~
wall.cpp:25:6: note: initializing argument 1 of 'void amin(ll&, ll)'
void amin(ll &a, ll b){ a=min(a,b); }
^~~~
wall.cpp:107:10: error: cannot bind non-const lvalue reference of type 'll& {aka long long int&}' to an rvalue of type 'll {aka long long int}'
amin(a.mx, b.mx);
~~^~
wall.cpp:25:6: note: initializing argument 1 of 'void amin(ll&, ll)'
void amin(ll &a, ll b){ a=min(a,b); }
^~~~
