글 읽기 - 시간초과 질문이 있습니다.

shinbian11 3년 전 0

어떤 부분에서 시간초과가 나는건가요? 트리의 크기나 배열에서 문제가 있는건가요? 시간복잡도에 문제가 있나요?

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
ll init_min(vl& arr, vl& tree, int node, int start, int end)
{
	if (start == end)
		return tree[node] = arr[start];

	ll mid = (start + end) / 2;
	return tree[node] = min(init_min(arr, tree, node * 2, start, mid),init_min(arr, tree, node * 2 + 1, mid + 1, end));
}
ll init_max(vl& arr, vl& tree, int node, int start, int end)
{
	if (start == end)
		return tree[node] = arr[start];

	ll mid = (start + end) / 2;
	return tree[node] = max(init_max(arr, tree, node * 2, start, mid), init_max(arr, tree, node * 2 + 1, mid + 1, end));
}
ll getMin(vl& tree, int node, int start, int end, int left, int right)
{
	if ((right < start) || (end < left))
		return -1;
	if ((left <= start) && (end <= right))
		return tree[node];
	int mid = (start + end) / 2;
	
	int one = getMin(tree, node * 2, start, mid, left, right);
	int two = getMin(tree, node * 2 + 1, mid + 1, end, left, right);
	if (one == -1)
		return getMin(tree, node * 2 + 1, mid + 1, end, left, right);
	else if (two == -1)
		return getMin(tree, node * 2, start, mid, left, right);
	else
		return min(getMin(tree, node * 2, start, mid, left, right), getMin(tree, node * 2 + 1, mid + 1, end, left, right));
}
ll getMax(vl& tree, int node, int start, int end, int left, int right)
{
	if ((right < start) || (end < left))
		return -1;
	if ((left <= start) && (end <= right))
		return tree[node];
	int mid = (start + end) / 2;

	int one = getMax(tree, node * 2, start, mid, left, right);
	int two = getMax(tree, node * 2 + 1, mid + 1, end, left, right);
	if (one == -1)
		return getMax(tree, node * 2 + 1, mid + 1, end, left, right);
	else if (two == -1)
		return getMax(tree, node * 2, start, mid, left, right);
	else
		return max(getMax(tree, node * 2, start, mid, left, right), getMax(tree, node * 2 + 1, mid + 1, end, left, right));
}

int main()
{

	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n, m;
	cin >> n >> m;
	int h = (int)ceil(log2(n));
	int tree_size = (1 << (h + 1));
	vl arr(n);
	vl tree1(tree_size);
	vl tree2(tree_size);
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
	}
	init_min(arr, tree1, 1, 0, n - 1); //트리(min) 만들기
	init_max(arr, tree2, 1, 0, n - 1); //트리(max) 만들기
	for (int i = 0; i < m; i++)
	{
		ll a, b;
		cin >> a >> b;
		cout << getMin(tree1, 1, 0, n - 1, a - 1, b - 1) << ' ';
		cout << getMax(tree2, 1, 0, n - 1, a - 1, b - 1) << '\n';
	}
}

djm03178 3년 전 1

one == -1이면 return two;를, two == -1이면 return one;을, 아니면 return min(one, two);를 하면 되는데 재귀 호출을 다시 하고 있는 것이 문제입니다.

shinbian11 3년 전 0

고맙습니다!

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

문제

문제

출처

ICPC

시간초과 질문이 있습니다.

shinbian11 3년 전 0

djm03178 3년 전 1

shinbian11 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말