Submission #901923

#	Time	Username	Problem	Language	Result	Execution time	Memory
901923		Muhammad_Aneeq	Wall (IOI14_wall)	C++17	61 / 100	513 ms	262144 KiB

wall

#include <iostream>
#include <algorithm>
#include "wall.h"
using namespace std;
struct seg
{
	int mi=0,ma=0,lazy=0;
	int ty=-1;	
};
int const MAXN=2e6;
seg* St[4*MAXN];
void push(int i)
{
	St[i*2]->lazy=St[i*2+1]->lazy=St[i]->lazy;
	St[i*2]->ty=St[i*2+1]->ty=St[i]->ty;
	St[i*2]->mi=St[i*2+1]->mi=St[i]->lazy;
	St[i*2]->ma=St[i*2+1]->ma=St[i]->lazy;
	St[i]->ty=-1;
}
void add(int i,int st,int en,int l,int r,int val)
{
	if (st>r||en<l)
		return;
	if (st>=l&&en<=r)
	{
		if (St[i]->mi>=val)
			return;
		if (St[i]->ma<=val)
		{
			St[i]->mi=St[i]->ma=val;
			St[i]->ty=-1;
			if (st!=en)
			{
				St[i*2]->lazy=St[i*2+1]->lazy=val;
				St[i*2]->ty=St[i*2+1]->ty=1;
				St[i*2]->mi=St[i*2+1]->mi=val;
				St[i*2]->ma=St[i*2+1]->ma=val;
			}
			return;
		}
	}
	if (St[i]->ty!=-1)
		push(i);
	int mid=(st+en)/2;
	add(i*2,st,mid,l,r,val);add(i*2+1,mid+1,en,l,r,val);
	St[i]->mi=min(St[i*2]->mi,St[i*2+1]->mi);
	St[i]->ma=max(St[i*2]->ma,St[i*2+1]->ma);
}
void sub(int i,int st,int en,int l,int r,int val)
{
	if (st>r||en<l)
		return;
	if (st>=l&&en<=r)
	{
		if (St[i]->ma<=val)
			return;
		if (St[i]->mi>=val)
		{
			St[i]->mi=St[i]->ma=val;
			St[i]->ty=-1;
			if (st!=en)
			{
				St[i*2]->lazy=St[i*2+1]->lazy=val;
				St[i*2]->ty=St[i*2+1]->ty=2;
				St[i*2]->mi=St[i*2+1]->mi=val;
				St[i*2]->ma=St[i*2+1]->ma=val;
			}
			return;
		}
	}
	if (St[i]->ty!=-1)
		push(i);
	int mid=(st+en)/2;
	sub(i*2,st,mid,l,r,val);sub(i*2+1,mid+1,en,l,r,val);
	St[i]->mi=min(St[i*2]->mi,St[i*2+1]->mi);
	St[i]->ma=max(St[i*2]->ma,St[i*2+1]->ma);
}
int get(int i,int r,int st,int en)
{
	if (st==en)
		return St[i]->mi;
	if (St[i]->ty!=-1)
		push(i);
	int mid=(st+en)/2;
	if (r<=mid)
		return get(i*2,r,st,mid);
	return get(i*2+1,r,mid+1,en);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	for (int i=0;i<4*n;i++)
	{
		St[i]=NULL;
		St[i]=new seg();
	}
	for (int i=0;i<k;i++)
	{
		if (op[i]==1)
			add(1,0,n-1,left[i],right[i],height[i]);
		else
			sub(1,0,n-1,left[i],right[i],height[i]);
	}
	for (int i=0;i<n;i++)
		finalHeight[i]=get(1,i,0,n-1);
}

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