Submission #1304089

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304089		activedeltorre	Wall (IOI14_wall)	C++20	100 / 100	493 ms	83460 KiB

wall

#include "wall.h"
#include <iostream>
using namespace std;
int maxim[4500005];
int minim[4500005];
int rez[2000005];
int lazy[4500005];
void build(int node,int st,int dr)
{
    minim[node]=0;
    maxim[node]=0;
    lazy[node]=-1;
    if(st!=dr)
    {
        int mij=(st+dr)/2;
        build(node*2,st,mij);
        build(node*2+1,mij+1,dr);
    }
}
void push(int node,int st,int dr)
{
    if(lazy[node]!=-1)
    {
        minim[node]=lazy[node];
        maxim[node]=lazy[node];
        if(st!=dr)
        {
            lazy[node*2]=lazy[node];
            lazy[node*2+1]=lazy[node];
        }
        lazy[node]=-1;
    }
}
void dfs(int node,int st,int dr)
{
    push(node,st,dr);
    if(st!=dr)
    {
        int mij=(st+dr)/2;
        dfs(node*2,st,mij);
        dfs(node*2+1,mij+1,dr);
    }
    else
    {
        rez[st]=maxim[node];
    }
}
void update(int node,int st,int dr,int qst,int qdr,int val,int tip)
{
    push(node,st,dr);
    if(st>dr || st>qdr || qst>dr || qst>qdr)
    {
        return;
    }
    if(qst<=st && dr<=qdr)
    {
        if(val>=maxim[node] || val<=minim[node])
        {
            if(val>=maxim[node] && tip==1)
            {
                lazy[node]=val;
                push(node,st,dr);
                return;
            }
            if(val<=minim[node] && tip==0)
            {
                lazy[node]=val;
                push(node,st,dr);
                return;
            }
            return;
        }
        else
        {
            int mij=(st+dr)/2;
            update(node*2,st,mij,qst,qdr,val,tip);
            update(node*2+1,mij+1,dr,qst,qdr,val,tip);
            maxim[node]=max(maxim[node*2],maxim[node*2+1]);
            minim[node]=min(minim[node*2],minim[node*2+1]);
            return;
        }
    }
    int mij=(st+dr)/2;
    update(node*2,st,mij,qst,qdr,val,tip);
    update(node*2+1,mij+1,dr,qst,qdr,val,tip);
    maxim[node]=max(maxim[node*2],maxim[node*2+1]);
    minim[node]=min(minim[node*2],minim[node*2+1]);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    build(1,1,n);
    for(int i=0;i<k;i++)
    {
        if(op[i]==2)
        {
            op[i]=0;
        }
        update(1,1,n,left[i]+1,right[i]+1,height[i],op[i]);
    }
    dfs(1,1,n);
    for(int i=1;i<=n;i++)
    {
        finalHeight[i-1]=rez[i];
    }
    return;
}

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