| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1139112 | Moonn | Wall (IOI14_wall) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define ll int
#define AI ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl "\n"
#define f first
#define s second
#define oo 1e18
#define lzs first
#define s1 second
using namespace std;
const int sz=2e6;
struct node
{
ll lzmi;
ll lzma;
node(): lzmi(0),lzma(1e9){};
};
ll v[sz];
node lz[sz*4];
ll ql,qr,t,x;
/*void mii(ll pos,ll mi,ll ma)
{
/// [] ()
/// () []
/// [()]
/// [(])
/// ([)]
if(lz[pos].lzmi<)
}*/
void relax(ll pos,ll l,ll r)
{
ll mi=lz[pos].lzmi;
ll ma=lz[pos].lzma;
lz[pos].lzmi=0;
lz[pos].lzma=1e9;
//cout<<l<<' '<<r<<mi<<' '<<ma<<endl;
if(l==r)
{
if(v[l]<mi)
v[l]=mi;
else if(v[l]>ma)
v[l]=ma;
// cout<<l<<' '<<v[l]<<endl;
return;
}
if(mi!=0)
{
lz[pos*2+1].lzmi=max(mi,lz[pos*2+1].lzmi);
lz[pos*2+2].lzmi=max(mi,lz[pos*2+2].lzmi);
}
lz[pos*2+1].lzma=max(lz[pos*2+1].lzma,lz[pos*2+1].lzmi);
lz[pos*2+2].lzma=max(lz[pos*2+2].lzma,lz[pos*2+2].lzmi);
if(ma!=1e9)
{
lz[pos*2+1].lzma=min(ma,lz[pos*2+1].lzma);
lz[pos*2+2].lzma=min(ma,lz[pos*2+2].lzma);
}
lz[pos*2+1].lzmi=min(lz[pos*2+1].lzma,lz[pos*2+1].lzmi);
lz[pos*2+2].lzmi=min(lz[pos*2+2].lzma,lz[pos*2+2].lzmi);
}
void upd(ll l,ll r,ll pos)
{
relax(pos,l,r);
if(ql>r or l>qr)
return;
if(ql<=l and r<=qr)
{
if(t==1)//add
{
lz[pos].lzmi=max(lz[pos].lzmi,x);
if(lz[pos].lzma<lz[pos].lzmi)
lz[pos].lzma=lz[pos].lzmi;
}
else
{
lz[pos].lzma=min(x,lz[pos].lzma);
if(lz[pos].lzmi>lz[pos].lzma)
lz[pos].lzmi=lz[pos].lzma;
}
relax(pos,l,r);
// cout<<l<<' '<<r<<"UPDD\n";
return;
}
ll mid=(l+r)/2;
upd(l,mid,pos*2+1);
upd(mid+1,r,pos*2+2);
}
void build(ll l,ll r,ll pos)
{
// cout<<l<<' '<<r<<lz[pos].lzmi<<' '<<lz[pos].lzma<<endl;
relax(pos,l,r);
if(l==r)
return;
ll mid=(l+r)/2;
build(l,mid,pos*2+1);
build(mid+1,r,pos*2+2);
}
void buildWall(ll n,ll k,ll op[],ll left[],ll right[],ll height[],ll finalHeight[])
{
for(ll i=0;i<k;i++)
{
t=op[i];
ql=left[i];
qr=right[i];
x=height[i];
upd(0,n-1,0);
// build(0,n-1,0);
/* for(ll i=0;i<n;i++)
cout<<v[i]<<' ';
cout<<endl;*/
}
build(0,n-1,0);
for(ll i=0;i<n;i++)
finalHeight[i]=v[i];
}
int main()
{
AI
ll n,k,m,i,j;
cin>>n>>k;
ll v1[k];
ll v2[k];
ll v3[k];
ll v4[k];
ll v5[n];
for(i=0;i<k;i++)
cin>>v1[i]>>v2[i]>>v3[i]>>v4[i];
buildWall(n,k,v1,v2,v3,v4,v5);
for(i=0;i<n;i++)
cout<<v5[i]<<' ';
}