Submission #162646

#	Time	Username	Problem	Language	Result	Execution time	Memory
162646		nafis_shifat	Wall (IOI14_wall)	C++14	61 / 100	683 ms	16872 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
#define f first
#define s second
using namespace std;
const int mx=2e5+10;
const int inf=1e9+10;
pii tree[4*mx];
int curval[4*mx];
void merge(int par,int kid)
{
	if(curval[par]!=-1)
	{
		curval[kid]=curval[par];
		tree[kid]={inf,-1};
		return;
	}

	if(curval[kid]!=-1)
	{
		if(curval[kid]<tree[par].s)
		{
			curval[kid]=tree[par].s;
		}
		else if(curval[kid]>tree[par].f)
		{
			curval[kid]=tree[par].f;
		}
		return;
	}
	tree[kid].f=min(tree[kid].f,tree[par].f);
	tree[kid].s=max(tree[kid].s,tree[par].s);
	
	if(tree[kid].f<=tree[kid].s)
	{
		if(tree[kid].f==tree[par].f)
		{
			curval[kid]=tree[kid].f;
		}
		else
		{
			curval[kid]=tree[kid].s;
		}
		tree[kid]={inf,-1};
		return;
	}
	curval[kid]=-1;

}
int query(int node,int b,int e,int p)
{
	if(curval[node]!=-1)
	{
	    return curval[node];
	}
	if(b==e)
	{
	    
		if(tree[node].s!=-1)return tree[node].s;
		return 0;
	}
	
	int mid=b+e>>1;
	int left=node<<1;
	int right=left|1;

	if(tree[node].f!=inf || tree[node].s!=-1)
	{
		merge(node,left);
		merge(node,right);
	}

	if(p<=mid)return query(left,b,mid,p);
	return query(right,mid+1,e,p);
}


void update(int node, int b,int e,int l,int r,int val,int type)
{
	if(b>r||e<l)return;


	if(b>=l && e<=r)
	{
		if(type==1)
		{
			if(curval[node]!=-1)
			{
				curval[node]=max(curval[node],val);
				return;
			}
			if(val>tree[node].f)
			{
				curval[node]=val;
				tree[node]={inf,-1};
				return;
			}
			tree[node].s=max(tree[node].s,val);
			curval[node]=-1;
		}		
		else
		{
			if(curval[node]!=-1)
			{
				curval[node]=min(curval[node],val);
				return;
			}
			if(val<tree[node].s)
			{
				curval[node]=val;
				tree[node]={inf,-1};
				return;
			}
			tree[node].f=min(tree[node].f,val);
			curval[node]=-1;
		}
		return;
	}
	
	int mid=b+e>>1;    
	int left=node<<1;
	int right=left|1;
	
	merge(node,left);
	merge(node,right);
	
	tree[node]={inf,-1};
	curval[node]=-1;

	
	update(left,b,mid,l,r,val,type);
	update(right,mid+1,e,l,r,val,type);


}





void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	for(int i=0;i<k;i++)
	{
		int l=left[i]+1;
		int r=right[i]+1;
		int v=height[i];
		update(1,1,n,l,r,v,op[i]);
	}
	for(int i=0;i<n;i++)finalHeight[i]=query(1,1,n,i+1);
  return;
}

Compilation message (stderr)

wall.cpp: In function 'int query(int, int, int, int)':
wall.cpp:65:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=b+e>>1;
          ~^~
wall.cpp: In function 'void update(int, int, int, int, int, int, int)':
wall.cpp:122:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=b+e>>1;    
          ~^~

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