oj.uz

Submission #725062

# Submission time Handle Problem Language Result Execution time Memory
725062 2023-04-16T16:12:08 Z sofija6 Wall (IOI14_wall) C++14
100 / 100
 993 ms 102416 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 440 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 8 ms 980 KB Output is correct
5 Correct 6 ms 1028 KB Output is correct
6 Correct 6 ms 1076 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 133 ms 8324 KB Output is correct
3 Correct 225 ms 4900 KB Output is correct
4 Correct 587 ms 12972 KB Output is correct
5 Correct 288 ms 13644 KB Output is correct
6 Correct 305 ms 13604 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 312 KB Output is correct
4 Correct 9 ms 1084 KB Output is correct
5 Correct 6 ms 980 KB Output is correct
6 Correct 7 ms 1076 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 144 ms 13828 KB Output is correct
9 Correct 211 ms 8524 KB Output is correct
10 Correct 598 ms 22524 KB Output is correct
11 Correct 299 ms 23564 KB Output is correct
12 Correct 278 ms 21920 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 150 ms 13932 KB Output is correct
15 Correct 39 ms 2516 KB Output is correct
16 Correct 778 ms 22612 KB Output is correct
17 Correct 280 ms 22092 KB Output is correct
18 Correct 288 ms 21996 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 12 ms 980 KB Output is correct
5 Correct 6 ms 980 KB Output is correct
6 Correct 6 ms 1100 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 140 ms 13900 KB Output is correct
9 Correct 223 ms 8440 KB Output is correct
10 Correct 594 ms 22468 KB Output is correct
11 Correct 303 ms 23488 KB Output is correct
12 Correct 264 ms 21888 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 148 ms 13868 KB Output is correct
15 Correct 44 ms 2516 KB Output is correct
16 Correct 744 ms 22612 KB Output is correct
17 Correct 286 ms 22044 KB Output is correct
18 Correct 276 ms 22012 KB Output is correct
19 Correct 946 ms 102288 KB Output is correct
20 Correct 945 ms 99944 KB Output is correct
21 Correct 931 ms 102308 KB Output is correct
22 Correct 964 ms 99776 KB Output is correct
23 Correct 960 ms 99852 KB Output is correct
24 Correct 967 ms 99924 KB Output is correct
25 Correct 951 ms 99724 KB Output is correct
26 Correct 939 ms 102348 KB Output is correct
27 Correct 912 ms 102416 KB Output is correct
28 Correct 954 ms 99720 KB Output is correct
29 Correct 993 ms 99852 KB Output is correct
30 Correct 960 ms 99852 KB Output is correct