#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
struct ura {
int val;
vector<pii > lazy;
};
int n;
int alturas[100005];
ura ST[400005];
void agregar(int nodo, pii a) {
if (a.first == 3) {
while (!ST[nodo].lazy.empty())
ST[nodo].lazy.pop_back();
}
if (ST[nodo].lazy.empty()) {
ST[nodo].lazy.push_back(a);
return;
}
pii b;
for(int i=ST[nodo].lazy.size()-1; i>=0; i++) {
b = ST[nodo].lazy[i];
if (a.first == 1) {
if (b.first == 3) {
ST[nodo].lazy.push_back(a);
break;
} else if (b.first == 1) {
ST[nodo].lazy[i].second = max(a.second, b.second);
break;
} else {
if (b.second <= a.second) {
while (!ST[nodo].lazy.empty())
ST[nodo].lazy.pop_back();
ST[nodo].lazy.push_back({3, a.second});
break;
}
if (i-1 >= 0) {
if (ST[nodo].lazy[i-1].first == 1) {
b = ST[nodo].lazy[i-1];
ST[nodo].lazy[i-1] = ST[nodo].lazy[i];
ST[nodo].lazy[i] = {1, max(a.second, b.second)};
break;
}
}
ST[nodo].lazy.push_back(a);
}
} else {
if (b.first == 3) {
ST[nodo].lazy.push_back(a);
break;
} else if (b.first == 2) {
ST[nodo].lazy[i].second = min(a.second, b.second);
break;
} else {
if (b.second >= a.second) {
while (!ST[nodo].lazy.empty())
ST[nodo].lazy.pop_back();
ST[nodo].lazy.push_back({3, a.second});
break;
}
if (i-1 >= 0) {
if (ST[nodo].lazy[i-1].first == 2) {
b = ST[nodo].lazy[i-1];
ST[nodo].lazy[i-1] = ST[nodo].lazy[i];
ST[nodo].lazy[i] = {2, min(a.second, b.second)};
break;
}
}
ST[nodo].lazy.push_back(a);
}
}
}
}
void propagar(int nodo,int ini, int fin) {
while(!ST[nodo].lazy.empty()) {
pii la = ST[nodo].lazy.back();
if (la.first == 1)
ST[nodo].val = max(ST[nodo].val, la.second);
else if (la.first == 2)
ST[nodo].val = min(ST[nodo].val, la.second);
else
ST[nodo].val = la.second;
if (ini < fin) {
agregar(nodo*2, la);
agregar(nodo*2+1, la);
}
ST[nodo].lazy.pop_back();
}
}
void actualizar(int &a, int &b, int &h, int &inst, int nodo=1, int ini=0, int fin=n-1) {
propagar(nodo, ini, fin);
if (a > fin || b < ini) {
return;
}
if (a <= ini && fin <= b) {
agregar(nodo, {inst, h});
return;
}
int mid = (ini + fin) / 2;
actualizar(a, b, h, inst, nodo*2, ini, mid);
actualizar(a, b, h, inst, nodo*2+1, mid+1, fin);
propagar(nodo*2, ini, mid);
propagar(nodo*2+1, mid+1, fin);
}
void propagar_todo(int nodo=1, int ini=0, int fin=n-1) {
propagar(nodo, ini, fin);
if (ini == fin) {
alturas[ini] = ST[nodo].val;
return;
}
int mid = (ini + fin) / 2;
propagar_todo(nodo*2, ini, mid);
propagar_todo(nodo*2+1, mid+1, fin);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int k, inst, a, b, h;
cin >> n >> k;
while (k--) {
cin >> inst >> a >> b >> h;
actualizar(a, b, h, inst);
/// en inst:
/// 1 es para agregar, es decir, max(alt[i], h)
/// 2 es para quitar, es decir, min(alt[i], h)
}
propagar_todo();
for(int i=0; i<n; i++)
cout << alturas[i] << '\n';
return 0;
}
Compilation message
/usr/bin/ld: /tmp/cc7rjLNL.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccHCDBvM.o:wall.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc7rjLNL.o: in function `main':
grader.cpp:(.text.startup+0x133): undefined reference to `buildWall(int, int, int*, int*, int*, int*, int*)'
collect2: error: ld returned 1 exit status
