Submission #126511

#	Time	Username	Problem	Language	Result	Execution time	Memory
126511		tinjyu	Wall (IOI14_wall)	C++14	100 / 100	784 ms	101932 KiB

wall

#include "wall.h"
#include <iostream>
using namespace std;
long long int fh[10000005],mintree[10000005],maxtree[10000005],l,r,h;
int findtree(int s,int e,int t)
{
	if(mintree[t]==maxtree[t])
	{
		for(int i=s;i<=e;i++)
		{
			fh[i]=mintree[t];
		}
		return 0;
	}
	findtree(s,(s+e)/2,t*2);
	findtree((s+e)/2+1,e,t*2+1);
}
int add(int s,int e,int t)
{
	//cout<<maxtree[t]<<" "<<mintree[t]<<" "<<s<<" "<<e<<endl;
	if(r<s || l>e)return 0;
	if(l<=s && e<=r)
	{
		if(maxtree[t]<=h)
		{
			mintree[t]=h;
			maxtree[t]=h;
			return 0;
		}
		else if(mintree[t]>=h)return 0;
	}

	if(mintree[t]==maxtree[t])
	{
		maxtree[t*2]=mintree[t*2]=maxtree[t*2+1]=mintree[t*2+1]=maxtree[t];
	}
	add(s,(s+e)/2,t*2);
	add((s+e)/2+1,e,t*2+1);
	mintree[t]=min(mintree[t*2],mintree[t*2+1]);
	maxtree[t]=max(maxtree[t*2],maxtree[t*2+1]);
}
int rem(int s,int e,int t)
{
	//cout<<maxtree[t]<<" "<<mintree[t]<<" "<<s<<" "<<e<<endl;
	if(r<s || l>e)return 0;
	if(l<=s && e<=r)
	{
		if(mintree[t]>=h)
		{
			mintree[t]=h;
			maxtree[t]=h;
			return 0;
		}
		else if(maxtree[t]<=h)return 0;
	}
	if(mintree[t]==maxtree[t])
	{
		maxtree[t*2]=mintree[t*2]=maxtree[t*2+1]=mintree[t*2+1]=maxtree[t];
	}
	rem(s,(s+e)/2,t*2);
	rem((s+e)/2+1,e,t*2+1);
	mintree[t]=min(mintree[t*2],mintree[t*2+1]);
	maxtree[t]=max(maxtree[t*2],maxtree[t*2+1]);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  	for(int i=0;i<k;i++)
	{
		l=left[i],r=right[i],h=height[i];
		if(op[i]==1)add(0,n-1,1);
		else rem(0,n-1,1);
		
	}
	findtree(0,n-1,1);
		for(int i=0;i<n;i++)
		{
			finalHeight[i]=fh[i];
			//cout<<fh[i]<<" ";
		}
		//cout<<endl;
 	return;
}

Compilation message (stderr)

wall.cpp: In function 'int findtree(int, int, int)':
wall.cpp:17:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
wall.cpp: In function 'int add(int, int, int)':
wall.cpp:41:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
wall.cpp: In function 'int rem(int, int, int)':
wall.cpp:64:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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