글 읽기 - 시간초과가 납니다 ㅠㅠ 해결방법을 모르겠어요 ㅠㅠ

khj940829 4년 전 0

어떻게 해야할까요?

코드를 다시 짜야할까요??

#include <iostream>
#include <cstdio>
#include <ios>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <array>
#include <cmath>
#include <string>
#include <stdlib.h>
#include <numeric>

using namespace std;

long long int init(long long int* arr, vector<long long int>& tree, int node, int start, int end)
{
	if (start == end)
	{
		return tree[node] = arr[start];
	}
	else
	{
		return tree[node] = init(arr, tree, node * 2, start, (start + end) / 2) + init(arr, tree, node * 2 + 1, (start + end) / 2 + 1, end);
	}
}

long long int resultmin(vector<long long int> tree, int node, int start, int end, int minn, int maxx)
{
	if (minn > end || maxx < start)
	{
		return 9999999999;
	}
	if (start == end)
	{
		return tree[node];
	}
	if (start != end)
	{
		return min(resultmin(tree, node * 2, start, (start + end) / 2, minn, maxx), resultmin(tree, node * 2 + 1, (start + end) / 2 + 1, end, minn, maxx));
	}
}

long long int resultmax(vector<long long int> tree, int node, int start, int end, int minn, int maxx)
{
	if (minn > end || maxx < start)
	{
		return -1;
	}
	if (start == end)
	{
		return tree[node];
	}
	if (start != end)
	{
		return max(resultmax(tree, node * 2, start, (start + end) / 2, minn, maxx), resultmax(tree, node * 2 + 1, (start + end) / 2 + 1, end, minn, maxx));
	}
}

int main()
{
	long long int n, m;
	scanf("%lld %lld", &n, &m);
	long long int* a = new long long int[m];
	long long int* b = new long long int[m];
	long long int* arr = new long long int[n];
	long long int h = ceil(log2(n));
	long long int tree_size = (1 << (h + 1));
	vector<long long int> tree(tree_size);
	for (int i = 0; i < n; i++)
	{
		scanf("%lld", &arr[i]);
	}
	init(arr, tree, 1, 0, n - 1);
	for (int i = 0; i < m; i++)
	{
		scanf("%lld %lld", &a[i], &b[i]);
		printf("%lld %lld\n", resultmin(tree, 1, 0, n - 1, a[i] - 1, b[i] - 1), resultmax(tree, 1, 0, n - 1, a[i] - 1, b[i] - 1));
	}
	return 0;
}