Submission #843997

#	Time	Username	Problem	Language	Result	Execution time	Memory
843997		Mr_Ph	Wall (IOI14_wall)	C++14	100 / 100	1064 ms	92360 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
struct item
{
    int mn;
    int mx;
};
struct segtree
{
    int siz=1;
    vector<item>vals;
    vector<item>lazy;
    void init(int n)
    {
        while(siz<n)
            siz*=2;
        vals.resize(4*siz);
    }
    item mrg(item a,item b)
    {
        a.mn=min(a.mn,b.mn);
        a.mn=max(a.mn,b.mx);
        a.mx=max(a.mx,b.mx);
        a.mx=min(a.mx,b.mn);
        return a;
    }
    void updaterage(int l,int r,int v,int op,int x,int lx,int rx)
    {
        if(lx>r||rx<l)return ;
        if(lx>=l&&rx<=r)
        {
            if(op==1)
            {
                vals[x].mn=max(vals[x].mn,v);
                vals[x].mx=max(vals[x].mx,v);
            }
            else
            {
                vals[x].mn=min(vals[x].mn,v);
                vals[x].mx=min(vals[x].mx,v);
            }
            return;
        }

        vals[2*x+1]=mrg(vals[2*x+1],vals[x]);
        vals[2*x+2]=mrg(vals[2*x+2],vals[x]);
        vals[x].mn=1e9,vals[x].mx=0;
        int mid=(lx+rx+1)/2;
        updaterage(l,r,v,op,2*x+1,lx,mid-1);
        updaterage(l,r,v,op,2*x+2,mid,rx);
    }
    void updaterage(int l,int r,int v,int op)
    {
        updaterage(l,r,v,op,0,0,siz-1);
    }
    int calc(int l,int r,int x,int lx,int rx)
    {
        vals[2*x+1]=mrg(vals[2*x+1],vals[x]);
        vals[2*x+2]=mrg(vals[2*x+2],vals[x]);
        if(lx>r||rx<l)return 1e9;
        if(lx>=l&&rx<=r)return min(vals[x].mn,vals[x].mx);
        int mid=(lx+rx+1)/2;
        return min(calc(l,r,2*x+1,lx,mid-1),calc(l,r,2*x+2,mid,rx));
    }
    int calc(int l,int r)
    {
        return calc(l,r,0,0,siz-1);
    }
};
void buildWall(int n, int k, int x[], int l[], int r[], int h[], int ans[])
{
    segtree st;
    st.init(n);
    for(int i=0; i<k; i++)
    {
        st.updaterage(l[i],r[i],h[i],x[i]);
    }
    for(int i=0; i<n; i++)
        ans[i]=st.calc(i,i);
}

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