글 읽기 - 오답인데.. 알고리즘상에 틀린부분을 못찾겠네요 ㅠㅠ

temp 8년 전 0

해당문제를 세그먼트 트리로 해결했는데요.

음.. 어디서 틀렸는지 감이 안오네요. 이 사이트의 세그먼트 트리 소스를 참고하였습니다.

어느부분이 잘못되었을까요?

#include<iostream>
#include<vector>
#include<algorithm>
#define MAX 2100000000
using namespace std;
int init(vector<int> &arr, vector<int> &tree, int node, int start, int end)
{
	if (start == end) return tree[node] = arr[start];
	else return tree[node] = min(init(arr, tree, node * 2, start, (start + end) / 2), init(arr, tree, node * 2 + 1, (start + end) / 2 + 1, end));
}
int MIN(vector<int> &tree, int node, int start, int end, int left, int right)
{
	if (left > end || right < start) 
		return MAX;
	if (left <= start && end <= right)
		return tree[node];

	return min(MIN(tree, node * 2, start, (start + end) / 2, left, right), MIN(tree, node * 2 + 1, (start + end) / 2 + 1, end, left, right));
}
int main()
{
	int n, m, a, b;
	scanf("%d %d", &n, &m);
	vector<int> arr(100005), tree(200000);
	for (int i = 0; i < n; i++)
		scanf("%d", &arr[i]);

	init(arr, tree, 1, 0, n - 1);
	while (m--)
	{
		scanf("%d %d", &a, &b);
		printf("%d\n", MIN(tree, 1, 0, n - 1, a - 1, b - 1));
	}
	return 0;
}

leechhe 8년 전 1

tree의 크기를 더 크게 해야합니다.

Leaf 즉, a의 길이가 17일 때엔 노드 수가 1+2+4+8+16+32 = 63개가 필요합니다.

공간 복잡도는 A의 최대 길이의 3배 미만이 됩니다.

temp 8년 전 0

헐..감사합니다. 제가 계산 실수를 했었군요. 약 2.5배면 되겠구나 생각했네요.

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

문제

문제

출처

ICPC

오답인데.. 알고리즘상에 틀린부분을 못찾겠네요 ㅠㅠ

temp 8년 전 0

leechhe 8년 전 1

temp 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말