글 읽기 - seg tree로 최솟값 구하기

veydpz 7년 전 0

세그먼트 트리를 사용해서 시간 복잡도를 O(n + m lg(n)) 을 만들었는데, TLE가 뜹니다.

이전에 있었던 이 문제에 대한 질문의 댓글대로, 세그먼트 트리가 아니라 1000개씩 묶어서 최솟값 구해놓는 방법 또한 고려해 보았습니다만, O(n + m*n/1000)이므로 세그먼트 트리로 풀었을 때와 비슷한 속도를 보일 것 같습니다.

위의 두 방법 외에 더 좋은 방법이 있나요? ㅜㅜ 혹시 몰라서 세그먼트 트리로 푼 코드를 첨부합니다.

#include<stdio.h>
#include<algorithm>
#define INF 0x7fffffff
using namespace std;
int n,m;
int base = 1;
int arr[400010];
int p_min(int x,int y){
	int ret = INF;
	while(x != y){
		if(x%2 == 1){
			ret = min(ret, arr[x]);
			x++;
		}
		if(y%2 == 0){
			ret = min(ret, arr[y]);
			y--;
		}
		x /= 2;
		y /= 2;
	}
	if(x == y){
		ret = min(ret, arr[x]);
	}
	return ret;
}
int main(){
	scanf("%d%d",&n,&m);
	fill(arr,arr+400010,INF);
	while(base < n) base *= 2;
	for(int i=base;i<base+n;i++) scanf("%d",&arr[i]);
	for(int i=base-1;i>0;i--) arr[i] = min(arr[2*i], arr[2*i+1]);
	for(int i=1;i<=m;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		printf("%d\n",p_min(base+a-1,base+b-1));
	}
}

veydpz 7년 전 1

자문자답합니다. 10번째 줄에서 x!=y가 아니라 x<y 로 고쳐야 되네요. 아니면 무한루프 때문에 TLE...

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

문제

문제

출처

ICPC

seg tree로 최솟값 구하기 - 시간 초과

veydpz 7년 전 0

veydpz 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말