| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 514502 | enerelt14 | 벽 (IOI14_wall) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
int n, q;
struct node{
int lazy, mn, mx;
node(){
lazy=-1;
mn=0;
mx=0;
}
};
node tree[8000005];
void propagate(int id, int l, int r){
if (l==r)return;
if (tree[id].lazy!=-1){
tree[id*2+1].lazy=tree[id].lazy;
tree[id*2+2].lazy=tree[id].lazy;
tree[id*2+1].mn=tree[id].lazy;
tree[id*2+1].mx=tree[id].lazy;
tree[id*2+2].mn=tree[id].lazy;
tree[id*2+2].mx=tree[id].lazy;
}
tree[id].mn=min(tree[id*2+1].mn, tree[id*2+2].mn);
tree[id].mx=max(tree[id*2+1].mx, tree[id*2+2].mx);
tree[id].lazy=-1;
}
void update1(int id, int l, int r, int L, int R, int h){
if (L>r || l>R || tree[id].mn>=h)return;
if (L<=l && r<=R && tree[id].mn==tree[id].mx){
tree[id].lazy=max(tree[id].lazy, h);
tree[id].mn=max(tree[id].mn, h);
tree[id].mx=max(tree[id].mx, h);
//cout<<id<<" "<<l<<" "<<r<<" "<<tree[id].lazy<<" "<<tree[id].mn<<" "<<tree[id].mx<<"\n";
return;
}
propagate(id, l, r);
int m=(l+r)/2;
update1(id*2+1, l, m, L, R, h);
update1(id*2+2, m+1, r, L, R, h);
tree[id].mn=min(tree[id*2+1].mn, tree[id*2+2].mn);
tree[id].mx=max(tree[id*2+1].mx, tree[id*2+2].mx);
}
void update2(int id, int l, int r, int L, int R, int h){
if (L>r || l>R || tree[id].mx<=h)return;
if (L<=l && r<=R && tree[id].mn==tree[id].mx){
if (tree[id].lazy!=-1)tree[id].lazy=min(tree[id].lazy, h);
else tree[id].lazy=h;
tree[id].mn=min(tree[id].mn, h);
tree[id].mx=min(tree[id].mx, h);
//cout<<id<<" "<<l<<" "<<r<<" "<<tree[id].lazy<<" "<<tree[id].mn<<" "<<tree[id].mx<<"\n";
return;
}
propagate(id, l, r);
int m=(l+r)/2;
update2(id*2+1, l, m, L, R, h);
update2(id*2+2, m+1, r, L, R, h);
tree[id].mn=min(tree[id*2+1].mn, tree[id*2+2].mn);
tree[id].mx=max(tree[id*2+1].mx, tree[id*2+2].mx);
}
void solve(int id, int l, int r){
propagate(id, l, r);
if (l==r){
cout<<tree[id].mn<<"\n";
return;
}
int m=(l+r)/2;
solve(id*2+1, l, m);
solve(id*2+2, m+1, r);
}
int main(){
cin>>n>>q;
while(q--){
int x, y, z, t;
cin>>x>>y>>z>>t;
if (x==1)update1(0, 0, n-1, y, z, t);
else update2(0, 0, n-1, y, z, t);
}
solve(0, 0, n-1);
}