| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 289616 | tasfiq4 | 벽 (IOI14_wall) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/// #192
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int > pii;
typedef long long int lld;
#define pi acos(-1)
#define fr(i,m,n) for(i=m;i<n;i++)
#define fu(i,m,n) for(i=m;i>=n;i--)
#define vec vector<int>
#define pb push_back
#define pp pop_back()
#define ft first
#define sd second
#define all(v) v.begin(),v.end()
#define mom(ara) memset(ara,0,sizeof(ara));
#define m1m(ara) memset(ara,-1,sizeof(ara));
#define endl "\n"
#define eps 1.19209e-07
#define at1 (at*2)
#define at2 (at*2)+1
// add is true and remove is false
int A[5000000],B[5000000];
bool opt[5000000],mark[5000000];
int ans;
void change(int at,int h,bool w)
{
if(w)
{
if(h>A[at] || (!opt[at] && B[at]<h))
{
opt[at]=w;
A[at]=h;
mark[at]=true;
}
}
else
{
if(h<B[at] || (opt[at] && A[at]>h))
{
opt[at]=w;
B[at]=h;
mark[at]=true;
}
}
}
void propagate(int l,int r,int at)
{
mark[at]=false;
if(opt[at])
{
change(at1,B[at],false);
change(at2,B[at],false);
change(at1,A[at],true);
change(at2,A[at],true);
}
else
{
change(at1,A[at],true);
change(at2,A[at],true);
change(at1,B[at],false);
change(at2,B[at],false);
}
A[at]=0;B[at]=1e9+7;
}
void update(int l,int r,int at,int L,int R,int h,bool w)
{
if(l>R || r<L) return;
if(L<=l && r<=R)
{
change(at,h,w);
return;
}
if(mark[at]) propagate(l,r,at);
int mid=(l+r)/2;
update(l,mid,at1,L,R,h,w);
update(mid+1,r,at2,L,R,h,w);
}
void query(int l,int r,int at,int pos)
{
if(l==r)
{
if(mark[at])
{
if(opt[at])
{
ans=min(B[at],ans);
ans=max(A[at],ans);
}
else
{
ans=max(A[at],ans);
ans=min(B[at],ans);
}
}
return;
}
int mid=(l+r)/2;
if(pos<=mid) query(l,mid,at1,pos);
else query(mid+1,r,at2,pos);
if(mark[at])
{
if(opt[at])
{
ans=min(B[at],ans);
ans=max(A[at],ans);
}
else
{
ans=max(A[at],ans);
ans=min(B[at],ans);
}
}
}
int main()
{ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
int i,j,k,a,b,c,x,y,z,n,m,t;
cin>>n>>m;
fr(i,0,5000000) B[i]=1e9+7;
while(m--)
{
cin>>t>>x>>y>>z;
update(1,n,1,x+1,y+1,z,(t==1));
}
fr(i,1,n+1)
{
ans=0;
query(1,n,1,i);
cout<<ans<<endl;
}
}