#include <bits/stdc++.h>
//#include <wall.h>
#define pii pair <int, int>
#define pb push_back
#define F first
#define S second
using namespace std;
const int N = 2 * 1e6 + 10;
int over[N];
struct segtree {
vector <pii> tree;
vector <int> orin;
int sz;
void init(int n){
sz = 1;
while(sz < n) sz *= 2;
tree.assign(2 * sz - 1, {0, INT_MAX});
orin.assign(2 * sz - 1, 0);
}
void make(int x, int nt){
if(tree[x].F >= tree[nt].S){
tree[nt] = tree[x];
orin[x] = 1;
} else{
if(tree[x].S <= tree[nt].F){
tree[nt] = tree[x];
orin[x] = 2;
} else{
tree[nt].F = max(tree[nt].F, tree[x].F);
tree[nt].S = min(tree[nt].S, tree[x].S);
}
}
}
void prop(int x, int lx, int rx){
if(rx - lx == 1) return;
if(orin[x] != 0){
orin[2 * x + 1] = orin[2 * x + 2] = orin[x];
tree[2 * x + 1] = tree[2 * x + 2] = tree[x];
} else{
make(x, 2 * x + 1);
make(x, 2 * x + 2);
}
orin[x] = 0;
tree[x] = {0, INT_MAX};
}
void upd(int l, int r, int code, int val, int x, int lx, int rx){
if(l >= rx || lx >= r) return;
if(l <= lx && rx <= r){
if((code == 1 && val >= tree[x].S) || (code == 2 && val <= tree[x].F)){
orin[x] = code;
if(code == 1) tree[x] = {val, INT_MAX};
else tree[x] = {0, val};
} else{
if(code == 1) tree[x].F = max(tree[x].F, val);
else tree[x].S = min(tree[x].S, val);
}
return;
}
prop(x, lx, rx);
int mid = (lx + rx) / 2;
upd(l, r, code, val, 2 * x + 1, lx, mid);
upd(l, r, code, val, 2 * x + 2, mid, rx);
}
void upd(int l, int r, int code, int val){
upd(l, r, code, val, 0, 0, sz);
}
void get(int x, int lx, int rx, pii nt, int ntt){
if(ntt != 0){
tree[x] = nt;
orin[x] = ntt;
} else{
if(orin[x] == 0){
if(nt.F >= tree[x].S){
tree[x] = nt;
orin[x] = 1;
} else{
if(nt.S <= tree[x].F){
tree[x] = nt;
orin[x] = 2;
} else{
tree[x].F = max(tree[x].F, nt.F);
tree[x].S = min(tree[x].S, nt.S);
}
}
}
}
//cout << x << " "<< lx << " "<< rx << " " << local[x] << " " << cur[x].F << " "<< cur[x].S << endl;
if(rx - lx == 1){
//cout << orin[x] << " " << tree[x].F << endl;
if(orin[x] <= 1) over[lx] = tree[x].F;
else over[lx] = tree[x].S;
return;
}
int mid = (lx + rx) / 2;
get(2 * x + 1, lx, mid, tree[x], orin[x]);
get(2 * x + 2, mid, rx, tree[x], orin[x]);
}
void get(){
get(0, 0, sz, {0, INT_MAX}, 0);
}
};
void buildWall(int n, int k, int op[], int left[], int right[],
int h[], int ans[]){
for(int i = 0; i < n; i++){
ans[i] = 0;
}
segtree obj;
obj.init(n);
for(int i = 0; i < k; i++){
obj.upd(left[i], right[i] + 1, op[i], h[i]);
}
obj.get();
for(int i = 0; i < n; i++){
ans[i] = over[i];
}
}
int main (){
int n, k;
cin >> n >> k;
int op[k], left[k], right[k], h[k], ans[n];
for(int i = 0; i < k; i++){
cin >> op[i] >> left[i] >> right[i] >> h[i];
}
buildWall(n, k, op, left, right, h, ans);
for(int i = 0; i < n; i++){
cout << ans[i] << " ";
}
return 0;
}
Compilation message
/usr/bin/ld: /tmp/cc8aiDbB.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccNS7fMD.o:wall.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
