| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1131723 | Muhammet | 벽 (IOI14_wall) | C++17 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define ll long long
const int N = 2e6+5;
int n, m, stmx[N*4], stmn[N*4], lzmn[N*4], lzmx[N*4];
void f(int nd, int l, int r) {
if(l != r) {
stmn[nd*2] = max(stmn[nd*2], stmn[nd]), stmx[nd*2] = max(stmx[nd*2], stmn[nd]),
stmx[nd*2] = min(stmx[nd*2], stmx[nd]), stmn[nd*2] = min(stmn[nd*2], stmx[nd]);
stmn[nd*2+1] = max(stmn[nd*2+1], stmn[nd]), stmx[nd*2+1] = max(stmx[nd*2+1], stmn[nd]),
stmx[nd*2+1] = min(stmx[nd*2+1], stmx[nd]), stmn[nd*2+1] = min(stmn[nd*2+1], stmx[nd]);
}
return;
}
void upd(int nd, int l, int r, int x, int y, int h, int t) {
f(nd, l, r);
if(l > y or r < x) return;
if(l >= x and r <= y) {
if(t == 1) stmn[nd] = max(stmn[nd], h), stmx[nd] = max(stmx[nd], h);
else stmx[nd] = min(stmx[nd], h), stmn[nd] = min(stmn[nd], h);
f(nd, l, r);
return;
}
int md = (l + r) / 2;
upd(nd*2,l,md,x,y,h,t), upd(nd*2+1,md+1,r,x,y,h,t);
stmn[nd] = min(stmn[nd*2], stmn[nd*2+1]);
stmx[nd] = max(stmx[nd*2], stmx[nd*2+1]);
}
void fnd(int nd, int l, int r){
f(nd, l, r);
if(l == r) {
cout << stmn[nd] << '\n';
return;
}
int md = (l + r) / 2;
fnd(nd*2,l,md), fnd(nd*2+1,md+1,r);
return;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> n >> m;
while(m--) {
int t, l, r, h;
cin >> t >> l >> r >> h;
upd(1,1,n,l+1,r+1,h,t);
}
fnd(1,1,n);
return 0;
}