제출 #901913

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
901913		Muhammad_Aneeq	벽 (IOI14_wall)	C++17	61 / 100	482 ms	33248 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=1e5;
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)
	{
		// cout<<r<<' '<<st<<'\n';
		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<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