Submission #43765

#	Time	Username	Problem	Language	Result	Execution time	Memory
43765		faustaadp	Wall (IOI14_wall)	C++14	100 / 100	886 ms	262144 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll i,mi[8080808],ma[8080808],h[2020202];
bool lz[8080808];
void tum(ll aa,ll bb,ll cc)
{
	mi[aa]=min(mi[aa],bb);
	ma[aa]=min(ma[aa],bb);
	ma[aa]=max(ma[aa],cc);
}
void upd(ll aa,ll bb,ll cc,ll dd,ll ee,ll ff,ll gg)
{
	if(aa==bb)
		h[aa]=ma[ee];
	else
	if(lz[ee])
	{
		lz[ee]=0;
		lz[ee*2]=1;
		lz[ee*2+1]=1;
		tum(ee*2,mi[ee],ma[ee]);
		tum(ee*2+1,mi[ee],ma[ee]);
		mi[ee]=1e17;
		ma[ee]=0;		
	}
	if(bb<cc||dd<aa)
		return ;
	else
	if(cc<=aa&&bb<=dd)
	{
		lz[ee]=1;
		tum(ee,ff,gg);
	}
	else
	{
		ll ce=(aa+bb)/2;
		upd(aa,ce,cc,dd,ee*2,ff,gg);
		upd(ce+1,bb,cc,dd,ee*2+1,ff,gg);
	}
}
void final(ll aa,ll bb,ll ee)
{
	if(aa==bb)
	{
		h[aa]=ma[ee];
		return ;
	}
	else
	if(lz[ee])
	{
		lz[ee]=0;
		lz[ee*2]=1;
		lz[ee*2+1]=1;
		tum(ee*2,mi[ee],ma[ee]);
		tum(ee*2+1,mi[ee],ma[ee]);
		mi[ee]=1e17;
		ma[ee]=0;
	}
	ll ce=(aa+bb)/2;
	final(aa,ce,ee*2);
	final(ce+1,bb,ee*2+1);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for(i=1;i<=4*n;i++)
		mi[i]=1e17;
	for(i=0;i<k;i++)
	{
		if(op[i]==1)
			upd(0,n-1,left[i],right[i],1,1e17,height[i]);
		else
			upd(0,n-1,left[i],right[i],1,height[i],0);
	}
	final(0,n-1,1);
	for(i=0;i<n;i++)
		finalHeight[i]=h[i];
  	return ;
}

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