Submission #535259

#	Time	Username	Problem	Language	Result	Execution time	Memory
535259		smth	Wall (IOI14_wall)	C++14	0 / 100	295 ms	42752 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
int yci[4000003],yci2[4000002], mini[4000002],maxi[4000000], lazymin[4000000],lazymax[4000000],fin[2000002],tree[4000000];

void add(int le,int ri,int l,int r,int h, int ind)
{
    if(mini[ind]>=lazymin[ind])
    {
        mini[ind]=lazymin[ind];
        maxi[ind]=mini[ind];
       // tree[ind]=mini[ind];

         if(le!=ri)
        {
            lazymin[2*ind]=min(lazymin[2*ind],lazymin[ind]);
            lazymin[2*ind+1]=min(lazymin[2*ind+1],lazymin[ind]);
        }
        lazymin[ind]=100000000;
        if(mini[ind]==maxi[ind])tree[ind]=mini[ind];

    }
    if(l<=yci[le] && yci[ri]<=r)
    {
        if(maxi[ind]<=h)lazymax[ind]=max(lazymax[ind],h);
    }
    if(lazymax[ind] && maxi[ind]<=lazymax[ind])
    {
        maxi[ind]=lazymax[ind];
        mini[ind]=maxi[ind];
        //tree[ind]=maxi[ind];

        if(le!=ri)
        {
            lazymax[2*ind]=max(lazymax[2*ind],lazymax[ind]);
            lazymax[2*ind+1]=max(lazymax[2*ind+1],lazymax[ind]);

        }
        lazymax[ind]=0;
        if(mini[ind]==maxi[ind]){tree[ind]=mini[ind];}
    }
    if(l<=yci[le] && yci[ri]<=r)return;
    if(l>yci[ri] || r<yci[le])return;

    int mid=(le+ri)/2;

    add(le,mid,l,r,h,2*ind);
    add(mid+1,ri,l,r,h,2*ind+1);

    mini[ind]=min(mini[2*ind],mini[2*ind+1]);
    maxi[ind]=max(maxi[2*ind],maxi[2*ind+1]);

    if(mini[ind]==maxi[ind])tree[ind]=mini[ind];
}

void rem(int le,int ri,int l,int r,int h, int ind)
{
    if(lazymax[ind] && maxi[ind]<=lazymax[ind])
    {
        maxi[ind]=lazymax[ind];
        mini[ind]=maxi[ind];
        //tree[ind]=maxi[ind];

        if(le!=ri)
        {
            lazymax[2*ind]=max(lazymax[2*ind],lazymax[ind]);
            lazymax[2*ind+1]=max(lazymax[2*ind+1],lazymax[ind]);

        }
        lazymax[ind]=0;
        if(mini[ind]==maxi[ind]){tree[ind]=mini[ind];}
    }
    if(l<=yci[le] && yci[ri]<=r)
    {
        if(mini[ind]>=h)lazymin[ind]=min(lazymin[ind],h);
    }
    if(mini[ind]>=lazymin[ind])
    {
        mini[ind]=lazymin[ind];
        maxi[ind]=mini[ind];
       // tree[ind]=mini[ind];

         if(le!=ri)
        {
            lazymin[2*ind]=min(lazymin[2*ind],lazymin[ind]);
            lazymin[2*ind+1]=min(lazymin[2*ind+1],lazymin[ind]);
        }
        lazymin[ind]=100000000;
        if(mini[ind]==maxi[ind])tree[ind]=mini[ind];

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

    int mid=(le+ri)/2;

    rem(le,mid,l,r,h,2*ind);
    rem(mid+1,ri,l,r,h,2*ind+1);

    mini[ind]=min(mini[2*ind],mini[2*ind+1]);
    maxi[ind]=max(maxi[2*ind],maxi[2*ind+1]);

    if(mini[ind]==maxi[ind])tree[ind]=mini[ind];
}
void query(int le,int ri,int ind)
{
    if(tree[ind]!=0){

    //cout<<yci[le]<<" "<<yci[ri]<<" "<<maxi[ind]<<" "<<mini[ind]<<" "<<tree[ind]<<endl;
    for(int i=yci[le];i<=yci[ri];i++)fin[i-1]=tree[ind];
        if(maxi[ind]==mini[ind])return;
    }
    if(le==ri)return;
    int mid=(le+ri)/2;
    query(le,mid,2*ind);
    query(mid+1,ri,2*ind+1);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    long long i,le=1;

    for(i=0;i<k;i++)
    {
        left[i]++; right[i]++;
        yci2[2*i]=left[i];
        yci2[2*i+1]=right[i];
    }
    sort(yci2,yci2+2*k);

    for(i=0;i<2*k;i++)
    {
        if(i!=0 && i<2*n && yci2[i]==yci2[i-1])continue;
        yci[le++]=yci2[i];
    }

    for(i=0;i<4000000;i++)lazymin[i]=100000000;
    for(i=0;i<k;i++)
    {
        if(op[i]==1)add(1,le-1,left[i],right[i],height[i],1);
        else rem(1,le-1,left[i],right[i],height[i],1);
    }


    query(1,le-1,1);

    for(i=0;i<n;i++)finalHeight[i]=fin[i];

  return;
}

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