oj.uz

Submission #725003

# Submission time Handle Problem Language Result Execution time Memory
725003 2023-04-16T12:45:45 Z sofija6 Wall (IOI14_wall) C++14
24 / 100
 840 ms 13280 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<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);
        lazy2.resize(2*s+2,-1);
    }
    void Propagate_1(ll x,ll lx,ll rx)
    {
        if (lazy1[x]==-1)
            return;
        st[x].minn=max(st[x].minn,lazy1[x]);
        st[x].maxx=max(st[x].maxx,lazy1[x]);
        if (x<=s)
        {
            lazy1[2*x]=lazy1[2*x]==-1?lazy1[x] : max(lazy1[2*x],lazy1[x]);
            lazy1[2*x+1]=lazy1[2*x+1]==-1?lazy1[x] : max(lazy1[2*x+1],lazy1[x]);
        }
        lazy1[x]=-1;
    }
    void Propagate_2(ll x,ll lx,ll rx)
    {
        if (lazy2[x]==-1)
            return;
        st[x].minn=min(st[x].minn,lazy2[x]);
        st[x].maxx=min(st[x].maxx,lazy2[x]);
        if (x<=s)
        {
            lazy2[2*x]=lazy2[2*x]==-1?lazy2[x] : min(lazy2[2*x],lazy2[x]);
            lazy2[2*x+1]=lazy2[2*x+1]==-1?lazy2[x] : min(lazy2[2*x+1],lazy2[x]);
        }
        lazy2[x]=-1;
    }
    void Add(ll l,ll r,pair<ll,ll> val,ll x,ll lx,ll rx)
    {
        Propagate_1(x,lx,rx);
        Propagate_2(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)
    {
        Propagate_1(x,lx,rx);
        Propagate_2(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.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 3 ms 332 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 138 ms 8040 KB Output is correct
3 Correct 257 ms 4660 KB Output is correct
4 Correct 840 ms 12816 KB Output is correct
5 Correct 307 ms 13276 KB Output is correct
6 Correct 289 ms 13280 KB Output is correct

Subtask #3
0 / 29.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 -

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 -