oj.uz

답안 #901917

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
901917 2024-01-10T04:08:41 Z Muhammad_Aneeq 벽 (IOI14_wall) C++17
0 / 100
 2 ms 348 KB 
#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<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<4*n;i++)
		St[i]=new seg();
	for (int i=0;i<n;i++)
		finalHeight[i]=get(1,i,0,n-1);
}

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -