글 읽기 - 먹이사슬 질문 합니다.

hj_d 7년 전 0

제가 sort 하고 이분 탐색으로 답을 구했는데 제가 보기에는 N log N 의 시간이 걸린다고 생각 하는데 시간 초과가 뜨더라구요.

답은 잘 맞는데, 어디서 시간 초과가 나는지 모르겠습니다. 알려주세요 ㅜㅜ

#include<stdio.h>
#include<algorithm>
using namespace std;

struct ani{
	int x, y;
};
bool com(ani a, ani b) {
	if (a.x == b.x)
		return a.y > b.y;
	return a.x < b.x;
}
ani list[500001];
int dp[500001];
int n;
int main()
{
	int num, i;
	int ans = 0;
	int ro, lo, mid;
	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d %d %d", &num, &list[i].x, &list[i].y);
	sort(list, list + n, com);
	for (i = 0; i < n; i++)
	{
		lo = 0;
		ro = ans;
		if (ro == lo)
			mid = 0;
		else
		{
			while (lo <= ro)
			{
				mid = (ro + lo) / 2;
				if (dp[mid] >= list[i].y)
					lo++;
				else
					ro--;
			}
		}
		if (mid == ans)
			dp[ans++] = list[i].y;
		else
			dp[mid] = list[i].y;
	}
	printf("%d\n", ans);
}

wowoto9772 7년 전 0

바이너리 서치처럼 보이지만, O(n)정도 되는거같아요.

lo++, ro--가 문제가 될거같아요.

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

문제

문제

출처

ICPC

먹이사슬 질문 합니다.

hj_d 7년 전 0

wowoto9772 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말