Submission #535282

#	Time	Username	Problem	Language	Result	Execution time	Memory
535282		daisy	Wall (IOI14_wall)	C++17	0 / 100	141 ms	12116 KiB

wall

#include<iostream>
#include<cstring>
#include<algorithm>
#include "wall.h"
using namespace std;
int a[1000005],y[1000005],tree[4000005],mi[4000005],ma[4000005],st[1000005],re[1000005];
int lazy1[4000005],lazy2[4000005];
bool b[1000005];
void update(int node,int l,int r,int le,int ri,int type,int h)
{
    if(le<=y[l] && y[r]<=ri)
    {
        if(type==1)
            lazy1[node]=max(lazy1[node],h);

        else lazy2[node]=min(lazy2[node],h);
    }
        if(l!=r)
        {
            lazy1[2*node]=max(lazy1[2*node],lazy1[node]);
            lazy1[2*node+1]=max(lazy1[2*node+1],lazy1[node]);

            lazy2[2*node]=min(lazy2[2*node],lazy2[node]);
            lazy2[2*node+1]=min(lazy2[2*node+1],lazy2[node]);
        }


    if((le<=y[l] && y[r]<=ri) || y[l]>ri || y[r]<le) return;

    int mid=(l+r)/2;

    update(2*node,l,mid,le,ri,type,h);
    update(2*node+1,mid+1,r,le,ri,type,h);
}
void updatefinal(int node,int l,int r)
{
        if(l!=r)
        {
            lazy1[2*node]=max(lazy1[2*node],lazy1[node]);
            lazy1[2*node+1]=max(lazy1[2*node+1],lazy1[node]);

            lazy2[2*node]=min(lazy2[2*node],lazy2[node]);
            lazy2[2*node+1]=min(lazy2[2*node+1],lazy2[node]);


            lazy1[2*node]=min(lazy1[2*node],lazy2[node]);
            lazy2[2*node]=max(lazy2[2*node],lazy1[node]);

            lazy1[2*node+1]=min(lazy1[2*node+1],lazy2[node]);
            lazy2[2*node+1]=max(lazy2[2*node+1],lazy1[node]);
            lazy1[node]=-1;
            lazy2[node]=1000000;
        }

    if(l==r) {re[y[l]]=lazy1[node];return;}

    int mid=(l+r)/2;

    updatefinal(2*node,l,mid);
    updatefinal(2*node+1,mid+1,r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    for(int i=0;i<k;i++)
    {
        a[2*i]=left[i];
        a[2*i+1]=right[i];
    }
    sort(a,a+2*k);
    y[1]=a[0];
    int in=2;
    for(int i=1;i<2*k;i++)
    {
        if(a[i]!=a[i-1])
        {y[in]=a[i];in++;}
    }
    in--;
    for(int i=1;i<=in;i++) {lazy2[i]=1000000;lazy1[i]=-1;}
    for(int i=0;i<k;i++)
    {
        if(op[i]==1)  //adding
        {
            update(1,1,in,left[i],right[i],1,height[i]);
        }
        else  //removing
        {
            update(1,1,in,left[i],right[i],2,height[i]);
        }
    }
    updatefinal(1,1,in);
    int p=0,z=1;
    for(int i=0;i<n;i++)
    {
        if(y[z]==i) {p=i;z++;}
        finalHeight[i]=re[p];

    }
    return;
}
/*
10 6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0
*/

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