글 읽기 - 시간을 더 줄이기 위한 방법이 또 있을까요?

mushi 7년 전 0

ICPC 11년 대회문제 A 입니다.(https://icpcarchive.ecs.baylor...)

8900번 문제에서 삭제되고 없네요.

첨부된 소스는 step 1 인 블럭을 아래로 내리는 부분입니다.

y값을 기준으로 정렬후 이중 for문으로 내릴 블럭(i)이랑 이전에 내려진 블럭(j)들을 비교하여

조건에 따라 내릴 위치를 정합니다.

알고스팟에서 설명을 보니 세그먼트 트리로 구성시 로그시간에 해결 가능하다는데

제 소스에선 아마 저 2번째 for인 블럭 비교부분인거 같습니다.

각 스텝마다 시시각각 변하는 블럭위치를 어떻게 구간을 나눠서 세그먼트 트리로 구현하는 건가요?

flag=0;
            sort(c, c + n, comparey);
            for (i=0; i<n; i++)
			{
                t = 0;
                for (j=0; j<i; j++)
				{
                    if (c[j].x0 < c[i].x1 && c[i].x0 < c[j].x1)
					{
                        t = max(c[j].y1, t);
                    }
                }
                if (t != c[i].y0)
				{
                    flag = 1;
                    c[i].y1 -= (c[i].y0 - t);
                    c[i].y0 = t;
                }
            }

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

문제

문제

출처

ICPC

시간을 더 줄이기 위한 방법이 또 있을까요?

mushi 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말