Submission #724988

#	Time	Username	Problem	Language	Result	Execution time	Memory
724988		sofija6	Wall (IOI14_wall)	C++14	0 / 100	1 ms	212 KiB

wall

#include <bits/stdc++.h>
#define ll int
using namespace std;
ll s;
struct element
{
    ll minn=0,maxx=0;
};
struct seg_tree
{
    vector<element> st;
    vector<ll> lazy2,lazy3;
    void Init(ll n)
    {
        s=1;
        while (s<n)
            s <<= 1;
        st.resize(2*s+2);
        lazy2.resize(2*s+2,-1);
        lazy3.resize(2*s+2,-1);
    }
    void Propagate_2(ll x,ll lx,ll rx)
    {
        if (lazy2[x]==-1)
            return;
        st[x].minn=max(st[x].minn,lazy2[x]);
        st[x].maxx=max(st[x].maxx,lazy2[x]);
        if (x<s)
        {
            lazy2[2*x]=lazy2[2*x]==-1?lazy2[x] : max(lazy2[2*x],lazy2[x]);
            lazy2[2*x+1]=lazy2[2*x+1]==-1?lazy2[x] : max(lazy2[2*x+1],lazy2[x]);
        }
        lazy2[x]=-1;
    }
    void Propagate_3(ll x,ll lx,ll rx)
    {
        if (lazy3[x]==-1)
            return;
        st[x].minn=min(st[x].minn,lazy3[x]);
        st[x].maxx=min(st[x].maxx,lazy3[x]);
        if (x<s)
        {
            lazy3[2*x]=lazy3[2*x]==-1?lazy3[x] : min(lazy3[2*x],lazy3[x]);
            lazy3[2*x+1]=lazy3[2*x+1]==-1?lazy3[x] : min(lazy3[2*x+1],lazy3[x]);
        }
        lazy3[x]=-1;
    }
    void Add(ll l,ll r,pair<ll,ll> val,ll x,ll lx,ll rx)
    {
        Propagate_2(x,lx,rx);
        Propagate_3(x,lx,rx);
        if (lx>r || rx<l)
            return;
        if (lx>=l && rx<=r)
        {
            if (val.first==2)
                lazy2[x]=val.second;
            else
                lazy3[x]=val.second;
            Propagate_2(x,lx,rx);
            Propagate_3(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);
        st[x]={min(st[2*x].minn,st[2*x+1].minn),max(st[2*x].maxx,st[2*x+1].maxx)};
    }
    ll Calc(ll pos,ll x,ll lx,ll rx)
    {
        Propagate_2(x,lx,rx);
        Propagate_3(x,lx,rx);
        if (st[x].minn==st[x].maxx)
            return st[x].minn;
        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]=S.Calc(i+1,1,1,s);
}

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