글 읽기 - 메모리 초과 없이 AC인 이유가 궁금합니다.

bliss08 1년 전 0

제가 궁금한 바는 꼭 이 문제에만 국한되는 건 아닌 것 같습니다. 세그먼트 트리의 크기가 2^N(N <= 100000)이나 되는데 3456KB로 통과되는 이유가 궁금하네요...

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

using namespace std;

int N, M;

int Arr[100001]{ 0 };

vector<int> Tree;

int Tree_Init(int Tree_Node, int Start, int End)
{
	if (Start == End)
		return Tree[Tree_Node] = Arr[Start];

	int L = Tree_Node * 2, R = L + 1, Mid = (Start + End) / 2;

	return Tree[Tree_Node] = min(Tree_Init(L, Start, Mid), Tree_Init(R, Mid + 1, End));
}

int Search_Minimum(int Tree_Node, int Start, int End, int Cmd_a, int Cmd_b)
{
	if (End < Cmd_a || Start > Cmd_b)
		return INT_MAX;

	if (Cmd_a <= Start && End <= Cmd_b)
		return Tree[Tree_Node];

	int L = Tree_Node * 2, R = L + 1, Mid = (Start + End) / 2;

	return min(Search_Minimum(L, Start, Mid, Cmd_a, Cmd_b), Search_Minimum(R, Mid + 1, End, Cmd_a, Cmd_b));
}

int main()
{
	fastio;

	cin >> N >> M;

	for (int i = 0; i < N; i++)
		cin >> Arr[i];

	int height = ceil(log2(N));

	Tree.resize(1 << (height + 1));

	Tree_Init(1, 0, N - 1);

	for (int i = 0; i < M; i++)
	{
		int a, b; cin >> a >> b;
		cout << Search_Minimum(1, 0, N - 1, a - 1, b - 1) << '\n';
	}
}

pill27211 1년 전 1

세그먼트 트리의 크기는 트리의 높이를 h라 할 때 2^N이 아니라 2^(h + 1)입니다.

이 때 h는 ceil(logN)이죠.

bliss08 1년 전 1

오우 ㅋㅋㅋㅋㅋㅋㅋ..... 정신이 없었나봅니다 ㅋㅋㅋㅋ 감사합니다 :)

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

문제

문제

출처

ICPC

메모리 초과 없이 AC인 이유가 궁금합니다.

bliss08 1년 전 0

pill27211 1년 전 1

bliss08 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말