Submission #109996

#	Time	Username	Problem	Language	Result	Execution time	Memory
109996		boatinw99	Wall (IOI14_wall)	C++11	100 / 100	1046 ms	114040 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
using namespace std ;
typedef pair<int,int> pii ;
#define mid (l+r>>1)
#define fi first
#define se second
const int N = 2e6+9 ,inf = 2e9;
int st[N<<2],ans[N];
pii lazy[N<<2];
void operate(pii &a,pii b)
{
    if(b.se<=a.fi)
    {
        a={b.se,b.se};
    }
    else if(a.se<=b.fi)
    {
        a={b.fi,b.fi};
    }
    else
    {
        a.fi=max(a.fi,b.fi);
        a.se=min(a.se,b.se);
    }
}
void push(int l,int r,int m)
{
    ///fi -> min ||| se -> max
    if(lazy[m].fi==-inf&&lazy[m].se==inf)return ;
    //printf("bbb l=%d r=%d (%d %d) \n",l,r,lazy[m].fi,lazy[m].se);
    st[m]=max(st[m],lazy[m].fi);
    st[m]=min(st[m],lazy[m].se);
    if(l<r)
    {
        operate(lazy[m<<1],lazy[m]);
        operate(lazy[m<<1|1],lazy[m]);
    }
    lazy[m]={-inf,inf};
}
void update(int l,int r,int x,int y,pii nw,int m)
{
    push(l,r,m);
    if(r<x||l>y)return ;
    if(l>=x&&r<=y)
    {
        lazy[m]=nw;
        //printf("aaa l=%d r=%d (%d %d) \n",l,r,lazy[m].fi,lazy[m].se);
        push(l,r,m);
        return ;
    }
    update(l,mid,x,y,nw,m<<1);
    update(mid+1,r,x,y,nw,m<<1|1);
}
void getans(int l,int r,int m)
{
    push(l,r,m);
    if(l==r)
    {
        ans[l]=st[m];
        return ;
    }
    getans(l,mid,m<<1);
    getans(mid+1,r,m<<1|1);
}
void buildWall(int n,int k,int op[],int left[],
               int right[],int height[],int finalHeight[])
{
    for(int i=0;i<N*4;i++)lazy[i]={-inf,inf};
    for(int i=0;i<k;i++)
    {
        int l = left[i] , r = right[i] ;
        if(op[i]==1)update(0,n-1,l,r,{height[i],inf},1);
        else update(0,n-1,l,r,{-inf,height[i]},1);
    }
    getans(0,n-1,1);
    for(int i=0;i<n;i++)finalHeight[i]=ans[i];
    return ;
}

Compilation message (stderr)

wall.cpp: In function 'void update(int, int, int, int, pii, int)':
wall.cpp:5:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
wall.cpp:52:14: note: in expansion of macro 'mid'
     update(l,mid,x,y,nw,m<<1);
              ^~~
wall.cpp:5:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
wall.cpp:53:12: note: in expansion of macro 'mid'
     update(mid+1,r,x,y,nw,m<<1|1);
            ^~~
wall.cpp: In function 'void getans(int, int, int)':
wall.cpp:5:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
wall.cpp:63:14: note: in expansion of macro 'mid'
     getans(l,mid,m<<1);
              ^~~
wall.cpp:5:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
wall.cpp:64:12: note: in expansion of macro 'mid'
     getans(mid+1,r,m<<1|1);
            ^~~

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