| # | Time | Username | Problem | Language | Result | Execution time | Memory | 
|---|---|---|---|---|---|---|---|
| 1139113 | Moonn | 벽 (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]<<' ';
}*//
