글 읽기 - 시간 초과가 나는데 자료구조를 잘못 선택한건가요?

ryudonghun1127 4년 전 0

어디서 시간을 줄일 수 있을지를 알고싶습니다. ㅠㅠ 정올 1264번 문제로 해결했을때는 100이 떠서 괜찮을거같았는데 시간이 200ms정도 떴는데 여기서는 시간이 초과 됩니다 ㅜㅜ

#include <stdio.h>
#include <malloc.h>

#define WHITE (0)
#define BLACK (1)

typedef struct _node
{
	struct _node *l, *r;
	int sx, ex;
	int sy, ey;
	int bw;
}NODE;

NODE root;

void Insert_Space_Info(int x, int y)
{
	NODE *node = &root;
	while (node->l)
	{
		if (node->l->sx < x && x < node->l->ex && node->l->sy < y && y < node->l->ey)
			node = node->l;
		else
			node = node->r;
	}

	node->l = (NODE*)calloc(1, sizeof(NODE));
	node->r = (NODE*)calloc(1, sizeof(NODE));
	node->l->bw = node->r->bw = node->bw ^ 1;

	switch (node->bw)
	{
	case WHITE:
		node->l->sx = node->sx; node->l->ex = node->ex;
		node->l->sy = node->sy; node->l->ey = y;
		node->r->sx = node->sx; node->r->ex = node->ex;
		node->r->sy = y; node->r->ey = node->ey;
		break;
	case BLACK:
		node->l->sx = node->sx; node->l->ex = x;
		node->l->sy = node->sy; node->l->ey = node->ey;
		node->r->sx = x; node->r->ex = node->ex;
		node->r->sy = node->sy; node->r->ey = node->ey;
		break;
	}
}

int max_area = 0, min_area = 0x7fffffff;
void Find_Min_Max(NODE *node)
{
	int area;
	if (node->l == (NODE*)0)
	{
		area = (node->ex - node->sx) * (node->ey - node->sy);
		if (max_area < area) max_area = area;
		if (min_area > area) min_area = area;
		return;
	}

	Find_Min_Max(node->l);
	Find_Min_Max(node->r);
}


int main(void)
{
	int i;
	int W, H;
	int N;
	int x, y;

	scanf("%d %d", &W, &H);
	scanf("%d", &N);

	root.sx = root.sy = 0;
	root.ex = W, root.ey = H;
	root.bw = WHITE;

	for (i = 0; i < N; i++)
	{
		scanf("%d %d", &x, &y);
		Insert_Space_Info(x, y);
	}

	Find_Min_Max(&root);
	printf("%d %d\n", max_area, min_area);

	return 0;
}

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

문제

문제

출처

ICPC

시간 초과가 나는데 자료구조를 잘못 선택한건가요?

ryudonghun1127 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말