Submission #535276

#	Time	Username	Problem	Language	Result	Execution time	Memory
535276		daisy	Wall (IOI14_wall)	C++17	0 / 100	1041 ms	12036 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];
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]-1<=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]);//lazy1[node]=0;

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


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

    int mid=(l+r)/2;

    update(2*node,l,mid,le,ri,type,h);
    update(2*node+1,mid,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]);
        }

    if(l==r) 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];st[a[0]]=1;
    int in=2;
    for(int i=1;i<2*k;i++)
    {
        if(a[i]!=a[i-1])
        {y[in]=a[i];st[a[i]]=in;in++;}
    }
    in--;
    for(int i=1;i<=in;i++) lazy2[i]=1000000;
    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 d;
    for(int i=k-1;i>=0;i--)
    {
        d=left[i];
        for(int p=left[i];p<=right[i];p++)
        {
            if(st[p]!=0) d=p;
           // if(finalHeight[p] && finalHeight[y[st[p]+1]])
           //     {p=y[st[p]+1]-1;finalHeight[p]=1;continue;}
            if(b[p]) continue;
            b[p]=1;

            if(op[i]==1) finalHeight[p]=lazy1[st[d]];
            else {finalHeight[p]=lazy2[st[d]];}
        }
    }
    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