legendmic2   5년 전

segment tree를 활용했습니다!

예제의 내용은 출력이 잘 되는데 어떤 부분에서 오류가 발생하는지를 캐치하지 못하겠습니다ㅠㅠ

많은 도움 부탁드립니다! 감사합니다!

djm03178   5년 전

세그먼트 트리가 완전 이진 트리가 아니기 때문에 98번째 줄처럼 한 번에 위치를 찾는 것이 가능하지 않을 것 같습니다. 예를 들면 어떤 구간이 원소 3개를 담당하고 있다면, 그의 자식들 중 하나는 1개의 원소를 담당하고, 다른 하나는 2개의 원소를 담당하게 될 텐데, 2개의 원소를 담당하는 트리는 한 번 더 쪼개져야 하므로 서로 다른 레벨에 위치하게 됩니다.

예를 들면 1번과 같은 입력에서 잘못된 답을 출력하는 것을 볼 수 있습니다.

그리고 지금과 같은 방법으로는 곱셈 결과를 올바르게 저장할 수 없습니다. 구간이 매우 넓을 수 있기 때문에 오버플로가 얼마든지 발생합니다. 2번과 같은 입력에서 역시 오답을 출력합니다. 이 문제는 지금과 같은 단순 곱으로 푸는 것이 아니라, 부호만 잘 관리해서 풀어줘야 하는 문제입니다.

시간 초과가 나는 것은 입출력 때문으로 예상되는데, cin은 기본적으로 cout과 tie가 되어 있어 둘을 번갈아서 사용할 경우 매번 flush가 발생하므로 이와 같은 쿼리 문제에서는 매우 느리게 동작합니다. 그래서 프로그램이 시작할 때 cin,tie(NULL); 을 넣어주면 빨라집니다.

legendmic2   5년 전

@djm03178

지난번도 그렇고 이번에도 감사합니다ㅠㅠ 다시 한 번 코딩해보겠습니다!


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