Submission #725010

#	Time	Username	Problem	Language	Result	Execution time	Memory
725010		sofija6	Wall (IOI14_wall)	C++14	24 / 100	757 ms	15328 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<pair<ll,ll> > lazy1,lazy2;
    void Init(ll n)
    {
        s=1;
        while (s<n)
            s <<= 1;
        st.resize(2*s+2);
        lazy1.resize(2*s+2,{-1,-1});
        lazy2.resize(2*s+2,{-1,-1});
    }
    void Propagate_1(ll x,ll lx,ll rx)
    {
        if (lazy1[x].first==-1)
            return;
        st[x].minn=max(st[x].minn,lazy1[x].first);
        st[x].maxx=max(st[x].maxx,lazy1[x].first);
        if (x<s)
        {
            lazy1[2*x].first=lazy1[2*x].first==-1?lazy1[x].first : max(lazy1[2*x].first,lazy1[x].first);
            lazy1[2*x+1].first=lazy1[2*x+1].first==-1?lazy1[x].first : max(lazy1[2*x+1].first,lazy1[x].first);
        }
        lazy1[x]={-1,-1};
    }
    void Propagate_2(ll x,ll lx,ll rx)
    {
        if (lazy2[x].first==-1)
            return;
        st[x].minn=min(st[x].minn,lazy2[x].first);
        st[x].maxx=min(st[x].maxx,lazy2[x].first);
        if (x<s)
        {
            lazy2[2*x].first=lazy2[2*x].first==-1?lazy2[x].first : min(lazy2[2*x].first,lazy2[x].first);
            lazy2[2*x+1].first=lazy2[2*x+1].first==-1?lazy2[x].first : min(lazy2[2*x+1].first,lazy2[x].first);
        }
        lazy2[x]={-1,-1};
    }
    void Add(ll l,ll r,pair<ll,pair<ll,ll> > val,ll x,ll lx,ll rx)
    {
        if (lazy2[x].second==-1 || lazy1[x].second<lazy2[x].second)
        {
            Propagate_1(x,lx,rx);
            Propagate_2(x,lx,rx);
        }
        else
        {
            Propagate_2(x,lx,rx);
            Propagate_1(x,lx,rx);
        }
        if (lx>r || rx<l)
            return;
        if (lx>=l && rx<=r)
        {
            if (val.first==1)
                lazy1[x]=val.second;
            else
                lazy2[x]=val.second;
            Propagate_1(x,lx,rx);
            Propagate_2(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)
    {
        if (lazy2[x].second==-1 || lazy1[x].second<lazy2[x].second)
        {
            Propagate_1(x,lx,rx);
            Propagate_2(x,lx,rx);
        }
        else
        {
            Propagate_2(x,lx,rx);
            Propagate_1(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],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: 24 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39