Submission #565384

#	Time	Username	Problem	Language	Result	Execution time	Memory
565384		n0sk1ll	Wall (IOI14_wall)	C++14	100 / 100	786 ms	118828 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>

#define ff(i,a,b) for (int i=a;i<b;i++)
#define bff(i,a,b) for (int i=b-1;i>=a;i--)

using namespace std;
const int mod=1000000007;

int k=1;
int val[4444444];
int l[4444444],r[4444444];
int minw[4444444],maxw[4444444];

void Build(int n)
{
    while (k<n) k*=2;
    ff(i,0,k) l[i+k]=i,r[i+k]=i;
    bff(i,1,k) l[i]=l[2*i],r[i]=r[2*i+1];
    ff(i,1,2*k) minw[i]=mod,maxw[i]=-mod;
}

void Upd(int p)
{
    val[p]=min(val[p],minw[p]);
    val[p]=max(val[p],maxw[p]);
    if (p<k)
    {
        minw[2*p]=min(minw[2*p],minw[p]);
        minw[2*p+1]=min(minw[2*p+1],minw[p]);
        maxw[2*p]=min(maxw[2*p],minw[p]);
        maxw[2*p+1]=min(maxw[2*p+1],minw[p]);

        minw[2*p]=max(minw[2*p],maxw[p]);
        minw[2*p+1]=max(minw[2*p+1],maxw[p]);
        maxw[2*p]=max(maxw[2*p],maxw[p]);
        maxw[2*p+1]=max(maxw[2*p+1],maxw[p]);
    }
    minw[p]=mod,maxw[p]=-mod;
}

void Minw(int p, int ll, int rr, int x)
{
    if (ll>r[p] || rr<l[p]);
    else if (ll<=l[p] && rr>=r[p]) minw[p]=min(minw[p],x),maxw[p]=min(maxw[p],x),Upd(p);
    else Upd(p),Minw(2*p,ll,rr,x),Minw(2*p+1,ll,rr,x);
}

void Maxw(int p, int ll, int rr, int x)
{
    if (ll>r[p] || rr<l[p]);
    else if (ll<=l[p] && rr>=r[p]) maxw[p]=max(maxw[p],x),minw[p]=max(minw[p],x),Upd(p);
    else Upd(p),Maxw(2*p,ll,rr,x),Maxw(2*p+1,ll,rr,x);
}

void buildWall(int n, int q, int op[], int left[], int right[], int height[], int finalHeight[])
{
    Build(n);
    ff(i,0,q)
    {
        if (op[i]==1) Maxw(1,left[i],right[i],height[i]);
        else Minw(1,left[i],right[i],height[i]);
    }

    ff(i,1,2*k) Upd(i);
    ff(i,0,n) finalHeight[i]=val[i+k];
}

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