| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 638698 | ggoh | 벽 (IOI14_wall) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
typedef long long lint;
int n,m,op,x,y,z,B=1;
int h[1<<22],d[1<<22],u[1<<22];
void pushhard(int num)
{
h[num*2]=h[num*2+1]=h[num];
u[num*2]=u[num*2+1]=u[num];
d[num*2]=d[num*2+1]=d[num];
}
void pushsoft(int num)
{
int t=num*2;
if(h[t]==0)
{
h[t]=3;u[t]=u[num];d[t]=d[num];
}
else if(h[t]==1)
{
u[t]=max(u[t],u[num]);
if(u[t]>d[num]){
h[t]=2;d[t]=d[num];
}
}
else if(h[t]==2)
{
d[t]=min(d[t],d[num]);
if(d[t]<u[num]){
h[t]=1;u[t]=u[num];
}
}
else{
if(d[t]<u[num]){
h[t]=1;u[t]=u[num];
}
else if(d[num]<u[t]){
h[t]=2;d[t]=d[num];
}
else{
u[t]=max(u[t],u[num]);
d[t]=min(d[t],d[num]);
}
}
t=num*2+1;
if(h[t]==0)
{
h[t]=3;u[t]=u[num];d[t]=d[num];
}
else if(h[t]==1)
{
u[t]=max(u[t],u[num]);
if(u[t]>d[num]){
h[t]=2;d[t]=d[num];
}
}
else if(h[t]==2)
{
d[t]=min(d[t],d[num]);
if(d[t]<u[num]){
h[t]=1;u[t]=u[num];
}
}
else{
if(d[t]<u[num]){
h[t]=1;u[t]=u[num];
}
else if(d[num]<u[t]){
h[t]=2;d[t]=d[num];
}
else{
u[t]=max(u[t],u[num]);
d[t]=min(d[t],d[num]);
}
}
}
void push(int num){
if(h[num]==1||h[num]==2)pushhard(num);
if(h[num]==3)pushsoft(num);
h[num]=0;
}
void update(int num,int s,int e,int l,int r,int op,int v)
{
if(l>e||s>r)return ;
if(l<=s&&e<=r)
{
if(h[num]==0)
{
u[num]=-1e9;
d[num]=1e9;
if(op==1)u[num]=v;
else d[num]=v;
h[num]=3;
}
else if(h[num]==1)
{
if(op==1)
{
u[num]=max(u[num],v);
}
else
{
if(u[num]>v)
{
d[num]=v;
h[num]=2;
}
}
}
else if(h[num]==2)
{
if(op==2)
{
d[num]=min(d[num],v);
}
else
{
if(d[num]<v)
{
u[num]=v;
h[num]=1;
}
}
}
else
{
if(op==1)
{
u[num]=max(u[num],v);
if(u[num]>d[num])h[num]=1;
}
else{
d[num]=min(d[num],v);
if(u[num]>d[num])h[num]=2;
}
}
return ;
}
push(num);
update(num*2,s,(s+e)/2,l,r,op,v);
update(num*2+1,(s+e)/2+1,e,l,r,op,v);
}
int main()
{
scanf("%d%d",&n,&m);
while(B<n)B*=2;
h[1]=1;
u[1]=0;
for(int i=0;i<m;i++)
{
scanf("%d%d%d%d",&op,&x,&y,&z);
update(1,0,B-1,x,y,op,z);
}
for(int i=1;i<B;i++)
{
push(i);
}
for(int i=0;i<n;i++)
{
if(h[B+i]==1)printf("%d\n",u[B+i]);
else printf("%d\n",d[B+i]);
}
}