글 읽기 - 2433 BIT 풀이인데요, 출력초과라니..ㅠㅠ

portableangel 9년 전 0

min 트리, max 트리를 따로 만들고 min(i, i+m-1)과 max(i, i+m-1)의 차이가 c 이하이면 출력하는 O(nlogn) 코드입니다.

for 루프가 유한한데 출력초과가 나요. ㅠㅠ

민값, 맥스값을 구할 때 에러가 있다면 런타임에러 / TLE가 정상인 것 같은데

출력 초과라니.. ㅠㅠ

도움 부탁 드립니다!

#include <stdio.h>
#include <algorithm>

using namespace std;

int bt_min[2100000];
int bt_max[2100000];

void maketree_min(int l, int r)
{
	if(l==1)
		return;

	for(int i=l;i<r;i+=2)
		bt_min[i/2]=min(bt_min[i],bt_min[i+1]);

	maketree_min(l/2, r/2);
}

void maketree_max(int l, int r)
{
	if(l==1)
		return;

	for(int i=l;i<r;i+=2)
		bt_max[i/2]=max(bt_max[i],bt_max[i+1]);
}

int getmax(int l, int r, int cur)
{
	if(l>r)
		return cur;
	if(l==r)
		return max(cur, bt_max[l]);
	if(l%2==0&&r%2)
		return getmax(l/2, r/2, cur);
	if(l%2&&r%2)
		return getmax(l/2+1, r/2, max(cur, bt_max[l]));
	if(l%2==0&&r%2==0)
		return getmax(l/2, r/2-1, max(cur, bt_max[r]));
	if(l%2&&r%2==0)
		return getmax(l/2+1, r/2-1, max( max(cur, bt_max[l]), bt_max[r]) );
}

int getmin(int l, int r, int cur)
{
	if(l>r)
		return cur;
	if(l==r)
		return min(cur,bt_min[l]);
	if(l%2==0&&r%2)
		return getmin(l/2, r/2, cur);
	if(l%2&&r%2)
		return getmin(l/2+1, r/2, min(cur,bt_min[l]));
	if(l%2==0&&r%2==0)
		return getmin(l/2, r/2-1, min(cur,bt_min[r]));
	if(l%2&&r%2==0)
		return getmin(l/2+1, r/2-1, min( min(cur, bt_min[l]), bt_min[r]) );
}

int main()
{
	int n, m, c;

	scanf("%d %d %d",&n,&m,&c);

	int size=1;

	while(size<n)
		size=size<<1;

	for(int i=size;i<size+n;i++)
	{
		scanf("%d",&bt_min[i]);
		bt_max[i]=bt_min[i];
	}

	for(int i=size+n;i<size*2;i++)
	{
		bt_min[i]=1000001;
		bt_max[i]=-1;
	}

	maketree_min(size,size*2);
	maketree_max(size,size*2);

	bool f=false;

	for(int i=size;i+m-1<size+n;i++)
	{
		if(abs(getmax(i,i+m-1,-1)-getmin(i,i+m-1,1000001))<=c)
		{
			f=true;
			printf("%d\n",i-size+1);
		}
	}

	if(!f)
		puts("NONE");

	return 0;
}

h0ngjun7 9년 전 1

maketree_max()함수 아래부분에 maketree_max(l/2, r/2); 를 추가해주시면 AC나옵니다ㅎㅎ

portableangel 9년 전 0

맞았어요! 감사합니다!

어떻게 저런 실수를 했는데도 예제는 잘 나와서 헤맸네요 ㅋㅋㅋㅋ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

2433 BIT 풀이인데요, 출력초과라니..ㅠㅠ

portableangel 9년 전 0

h0ngjun7 9년 전 1

portableangel 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말