Submission #58093

#	Time	Username	Problem	Language	Result	Execution time	Memory
58093		zetapi	Wall (IOI14_wall)	C++14	100 / 100	1621 ms	65736 KiB

wall

//#include "wall.h"
#include "bits/stdc++.h"
using namespace std;

#define pb  push_back
#define mp  make_pair
#define ll  long long
#define itr ::iterator 

typedef pair<int,int>  pii;

const int MAX=5e6;

struct data
{
	int Min;
	int Max;
}   Seg[MAX];

void push(int node,int CurMin,int CurMax)
{
	if(Seg[node].Max>=CurMin and Seg[node].Min<=CurMax)
	{
		CurMin=max(CurMin,Seg[node].Min);
		CurMax=min(CurMax,Seg[node].Max);
	}
	else if(Seg[node].Min>CurMax)
	    CurMin=CurMax;
	else if(Seg[node].Max<CurMin)
		CurMax=CurMin;
	Seg[node].Min=CurMin;
	Seg[node].Max=CurMax;
	return ;
}

void Update(int low,int high,int node,int qlow,int qhigh,pii delta)
{
	if(low>high or qlow>qhigh or qhigh<low or qlow>high)
		return ;
	if(low>=qlow and high<=qhigh)
	{
		if(delta.second==1)
		{
			if(Seg[node].Min>delta.first)
				return ;
			Seg[node].Min=delta.first;
			Seg[node].Max=max(Seg[node].Min,Seg[node].Max);
		}
		else
		{
			if(Seg[node].Max<delta.first)
				return ;
			Seg[node].Max=delta.first;
			Seg[node].Min=min(Seg[node].Min,Seg[node].Max);
		}
		//cout<<"updated "<<low-1<<" "<<high-1<<" previous "<<CurMin<<"  "<<CurMax<<" now its value is "<<Seg[node].Min<<" "<<Seg[node].Max<<"\n";
		//cout<<low-1<<" Updated in path "<<high-1<<" "<<Seg[node].Min<<" "<<Seg[node].Max<<"\n";
		return ;
	}
	push(2*node,Seg[node].Min,Seg[node].Max);
	push(2*node+1,Seg[node].Min,Seg[node].Max);
	Seg[node].Min=0;
	Seg[node].Max=MAX;
	int mid=(low+high)/2;
	Update(low,mid,2*node,qlow,qhigh,delta);
	Update(mid+1,high,2*node+1,qlow,qhigh,delta);
	return ;
}


int query(int low,int high,int node,int X)
{
	//cout<<low-1<<" "<<high-1<<" "<<Seg[node].Min<<" "<<Seg[node].Max<<"ha ha "<<CurMin<<" "<<CurMax<<"\n";
	if(low==high)
		return Seg[node].Min;
	push(2*node,Seg[node].Min,Seg[node].Max);
	push(2*node+1,Seg[node].Min,Seg[node].Max);
	int mid=(low+high)/2;
	if(X>=low and X<=mid)
		return query(low,mid,2*node,X);
	else
		return query(mid+1,high,2*node+1,X);
}

//void buildWall(int n=10, int k=6, vector<int> op={1,2,2,1,1,2}, vector<int> left={1,4,3,0,2,6}, vector<int> right={8,9,6,5,2,7}, vector<int> height={4,1,5,3,5,0})
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	int N=n,K=k;
	for(int A=1;A<=3*N;A++)
	{
      if(A>=MAX)
		break;
       	Seg[A].Min=0;
		Seg[A].Max=MAX;
	}
	for(int A=0;A<K;A++)
	{
		Update(1,N,1,left[A]+1,right[A]+1,mp(height[A],op[A]));
			//if(A==K-1)
			//cout<<query(1,N,1,A+1)<<" ";
		//cout<<"\n";
		//break;
	}
	//Update(1,N,1,1,N,mp(5,1));
	//Update(1,N,1,1,1,mp(0,2));
	//cout<<query(1,N,1,1)<<"\n";
	//cout<<query(1,N,1,7,0,MAX);
	for(int A=0;A<N;A++)
			finalHeight[A]=query(1,N,1,A+1);
  	return;
}

/*signed main()
{
	ios_base::sync_with_stdio(false);

	buildWall();
	return 0;
}*/

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