Submission #725062

#	Time	Username	Problem	Language	Result	Execution time	Memory
725062		sofija6	Wall (IOI14_wall)	C++14	100 / 100	993 ms	102416 KiB

wall

#include <bits/stdc++.h>
#define ll int
using namespace std;
ll s;
struct element
{
    ll minn=INT_MIN,maxx=INT_MAX;
};
struct seg_tree
{
    vector<element> st,lazy;
    void Init(ll n)
    {
        s=1;
        while (s<n)
            s <<= 1;
        st.resize(2*s+2);
        lazy.resize(2*s+2);
    }
    void Propagate(ll x,ll lx,ll rx)
    {
        if (lazy[x].minn==INT_MIN && lazy[x].maxx==INT_MAX)
            return;
        if (lazy[x].minn!=INT_MIN)
        {
            st[x].minn=max(st[x].minn,lazy[x].minn);
            st[x].maxx=max(st[x].maxx,st[x].minn);
            if (x<s)
            {
                lazy[2*x].minn=max(lazy[2*x].minn,lazy[x].minn);
                lazy[2*x].maxx=max(lazy[2*x].minn,lazy[2*x].maxx);
                lazy[2*x+1].minn=max(lazy[2*x+1].minn,lazy[x].minn);
                lazy[2*x+1].maxx=max(lazy[2*x+1].minn,lazy[2*x+1].maxx);
            }
        }
        if (lazy[x].maxx!=INT_MAX)
        {
            st[x].maxx=min(st[x].maxx,lazy[x].maxx);
            st[x].minn=min(st[x].maxx,st[x].minn);
            if (x<s)
            {
                lazy[2*x].maxx=min(lazy[2*x].maxx,lazy[x].maxx);
                lazy[2*x].minn=min(lazy[2*x].minn,lazy[2*x].maxx);
                lazy[2*x+1].maxx=min(lazy[2*x+1].maxx,lazy[x].maxx);
                lazy[2*x+1].minn=min(lazy[2*x+1].minn,lazy[2*x+1].maxx);
            }
        }
        lazy[x]={INT_MIN,INT_MAX};
    }
    void Add(ll l,ll r,pair<ll,ll> val,ll x,ll lx,ll rx)
    {
        Propagate(x,lx,rx);
        if (lx>r || rx<l)
            return;
        if (lx>=l && rx<=r)
        {
            if (val.first==1)
                lazy[x]={val.second,INT_MAX};
            else
                lazy[x]={INT_MIN,val.second};
            Propagate(x,lx,rx);
            return;
        }
        ll mid=(lx+rx)/2;
        Add(l,r,val,2*x,lx,mid);
        Add(l,r,val,2*x+1,mid+1,rx);
    }
    element Calc(ll pos,ll x,ll lx,ll rx)
    {
        Propagate(x,lx,rx);
        if (lx==rx)
            return st[x];
        ll mid=(lx+rx)/2;
        if (pos<=mid)
            return Calc(pos,2*x,lx,mid);
        return Calc(pos,2*x+1,mid+1,rx);
    }
};
seg_tree S;
void buildWall(ll n,ll k,ll op[],ll left[],ll right[],ll height[],ll finalHeight[])
{
    S.Init(n);
    for (ll i=0;i<k;i++)
        S.Add(left[i]+1,right[i]+1,{op[i],height[i]},1,1,s);
    for (ll i=0;i<n;i++)
        finalHeight[i]=max(0,S.Calc(i+1,1,1,s).minn);
}

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39