글 읽기 - 시간초과.... 도저히 모르겠네요 ㅠ

graycoral 2년 전 0

아래와 같이 코드를 작성했는데... 어디서 타임아웃이 발생하는지 모르겠네요;;; 다른 질문들을 봐도

제대로 푼거 같은데..

#include <iostream>

using namespace std;
const int max_num = 120000;
int N; int M;
int arr[max_num];
int rangeMin[500000];
int rangeMax[500000];

#define MIN(a, b) ( a > b ? b: a)
#define MAX(a, b) ( a > b ? a: b);

int initMin(int left, int right, int node) {
	if (left == right) {
		return rangeMin[node] = arr[left];
	}

	int mid = (left + right) / 2;
	int leftMin = initMin(left, mid, node * 2);
	int rightMin = initMin(mid + 1, right, node * 2 + 1);

	return rangeMin[node] = MIN(leftMin, rightMin);
}

int initMax(int left, int right, int node) {
	if (left == right) {
		return rangeMax[node] = arr[left];
	}

	int mid = (left + right) / 2;
	int leftMax = initMax(left, mid, node * 2);
	int rightMax = initMax(mid + 1, right, node * 2 + 1);

	return rangeMax[node] = MAX(leftMax, rightMax);
}

//const int INF_NUM = std::numeric_limits<int>::max();
const int INF_NUM = 987654321;
const int MIN_NUM = 0;

int queryMin(int left, int right, int node, int leftNode, int rightNode) {
	if (left > rightNode || right < leftNode)	return INF_NUM;
	if (left <= leftNode && rightNode <= right)	return rangeMin[node];

	int mid = (leftNode + rightNode) / 2;
	int leftMin = queryMin(left, right, node * 2, leftNode, mid);
	int rightMin = queryMin(left, right, node * 2 + 1, mid + 1, rightNode);

	return MIN(leftMin, rightMin);

}

int queryMax(int left, int right, int node, int leftNode, int rightNode) {
	if (left > rightNode || right < leftNode)	return MIN_NUM;
	if (left <= leftNode && rightNode <= right)	return rangeMax[node];

	int mid = (leftNode + rightNode) / 2;

	int leftMax = queryMax(left, right, node * 2, leftNode, mid);
	int rightMax = queryMax(left, right, node * 2 + 1, mid + 1, rightNode);

	return MAX(leftMax, rightMax);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); 	cout.tie(NULL);

	freopen("2357_input.txt", "r", stdin);
	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}

	initMin(0, N - 1, 1);
	initMax(0, N - 1, 1);

	for (int i = 0; i < M; i++) {
		int left, right;
		cin >> left >> right;

		cout << queryMin(left - 1, right - 1, 1, 0, N - 1) \
			<< " " << queryMax(left - 1, right - 1, 1, 0, N - 1) << endl;
	}

	return 0;
}

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

문제

문제

출처

ICPC

시간초과.... 도저히 모르겠네요 ㅠ_ㅠ

graycoral 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말