oj.uz

Submission #725029

# Submission time Handle Problem Language Result Execution time Memory
725029 2023-04-16T13:17:51 Z sofija6 Wall (IOI14_wall) C++14
24 / 100
 841 ms 15312 KB 
#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)
        {
            if (lazy1[2*x].first==-1 || lazy1[x].first>lazy1[2*x].first || (lazy2[2*x].first!=-1 && lazy2[2*x].second>lazy1[2*x].second && lazy2[2*x].second<lazy1[x].second))
                lazy1[2*x]=lazy1[x];
            if (lazy1[2*x+1].first==-1 || lazy1[x].first>lazy1[2*x+1].first || (lazy2[2*x+1].first!=-1 && lazy2[2*x+1].second>lazy1[2*x+1].second && lazy2[2*x+1].second<lazy1[x].second))
                lazy1[2*x+1]=lazy1[x];
        }
        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)
        {
            if (lazy2[2*x].first==-1 || lazy2[x].first<lazy2[2*x].first || (lazy1[2*x].first!=-1 && lazy1[2*x].second>lazy2[2*x].second && lazy1[2*x].second<lazy2[x].second))
                lazy2[2*x]=lazy2[x];
            if (lazy2[2*x+1].first==-1 || lazy2[x].first<lazy2[2*x+1].first || (lazy1[2*x+1].first!=-1 && lazy1[2*x+1].second>lazy2[2*x+1].second && lazy1[2*x+1].second<lazy2[x].second))
                lazy2[2*x+1]=lazy2[x];
        }
        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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Incorrect 2 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 150 ms 8124 KB Output is correct
3 Correct 307 ms 5160 KB Output is correct
4 Correct 841 ms 14816 KB Output is correct
5 Correct 322 ms 15308 KB Output is correct
6 Correct 329 ms 15312 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 284 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Incorrect 2 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Incorrect 2 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -