Submission #843190

#	Time	Username	Problem	Language	Result	Execution time	Memory
843190		Mr_Ph	Wall (IOI14_wall)	C++17	0 / 100	103 ms	8112 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
struct segtree
{
    int siz=1;
    vector<int>vals;
    vector<pair<int,int>>lazy;
    void init(int n)
    {
        while(siz<n)
            siz*=2;
        vals.resize(2*siz);
        lazy.resize(2*siz);
    }
    void check(int l,int r,int x)
    {
        if(lazy[x].second==1)
        {
            vals[x]=max(vals[x],lazy[x].first);
            int v=lazy[x].first,what=lazy[x].second;
            if(l!=r)
            {
                if(lazy[2*x+1].first<v)
                    lazy[2*x+1]= {v,what};
                if(lazy[2*x+2].first<v)
                    lazy[2*x+2]= {v,what};
            }
            lazy[x]={0,0};
        }
        else if(lazy[x].second==2)
        {
            vals[x]=min(vals[x],lazy[x].first);
            int v=lazy[x].first,what=lazy[x].second;
            if(l!=r)
            {
                    lazy[2*x+1]= {v,what};
                    lazy[2*x+2]= {v,what};
            }
            lazy[x]={0,0};
        }
    }
    void updrng(int l,int r,int v,int what,int x,int lx,int rx)
    {
       // cout<<lx<<" "<<rx<<endl;
        check(lx,rx,x);
        if(lx>r||rx<l)
            return;
        if(lx>=l&&rx<=r)
        {
            vals[x]=v;
            if(lx!=rx)
            {
                vals[x]=v;
                if(what==1)
                {
                        lazy[2*x+1]= {v,what};
                        lazy[2*x+2]= {v,what};
                }
                else
                {
                        lazy[2*x+1]= {v,what};
                        lazy[2*x+2]= {v,what};
                }
            }
            return;
        }
        int mid=(lx+rx+1)/2;
        updrng(l,r,v,what,2*x+1,lx,mid-1);
        updrng(l,r,v,what,2*x+2,mid,rx);

    }
    void updrng(int l,int r,int v,int what)
    {
        updrng(l,r,v,what,0,0,siz-1);
    }
    int calc(int l,int r,int x,int lx,int rx)
    {
                check(lx,rx,x);
        if(lx>r||rx<l)return 0;
        if(lx>=l&&rx<=r)return vals[x];
        int mid=(lx+rx+1)/2;
        int e=calc(l,r,2*x+1,lx,mid-1),e1=calc(l,r,2*x+2,mid,rx);
        return e+e1;
    }
    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.updrng(l[i],r[i],h[i],x[i]);
    for(int i=0;i<n;i++)
        ans[i]=st.calc(i,i);
}

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