글 읽기 - 여기서 시간을 줄이고 싶은데 어떻게 해야 하나요.

sandrea 8년 전 0

인덱스 트리를 활용해서 구현을 해보았는데요. 채점 넣으면 2%에서 더이상 오르질 않네요...ㅠ

#include <iostream>
using namespace std;

unsigned int min_tree[300000] = { 0, };
unsigned int max_tree[300000] = { 0, };

int main()
{
	int N = 0, M = 0;
	int size = 1;
	int pos;
	int _size;
	unsigned int tmp;
	cin >> N >> M;

	while (size < N)
		size *= 2;

	//min_tree init
	for (int i = 0; i < 262145; i++)
		min_tree[i] = -1;

	for (int i = size; i < size + N; i++)
	{
		cin >> tmp;
		min_tree[i] = tmp;
		max_tree[i] = tmp;
	}

	//tree construct
	_size = size;
	pos = size;
	while (pos / 2 != 0)
	{
		if (min_tree[pos] < min_tree[pos + 1])
			min_tree[pos / 2] = min_tree[pos];
		else
			min_tree[pos / 2] = min_tree[pos+1];

		if (max_tree[pos] > max_tree[pos + 1])
			max_tree[pos / 2] = max_tree[pos];
		else
			max_tree[pos / 2] = max_tree[pos + 1];

		if (pos < size * 2 - 2)
			pos += 2;
		else
		{
			size /= 2;
			pos = size;
		}
	}

	//search
	for (int i = 0; i < M; i++)
	{
		int a = 0, b = 0;
		unsigned int _min = -1, _max = 0;
		cin >> a >> b;

		a = a + _size - 1;
		b = b + _size - 1;

		while (a < b)
		{
			if (a % 2 == 1)//left pointer is right child
			{
				_min = _min < min_tree[a] ? _min : min_tree[a];
				_max = _max > max_tree[a] ? _max : max_tree[a];
				a++;
			}
			if (b % 2 == 0)//right pointer is left child
			{
				_min = _min = _min < min_tree[b] ? _min : min_tree[b];
				_max = _max = _max > max_tree[b] ? _max : min_tree[b];
				b--;
			}
			a /= 2;
			b /= 2;
		}

		if (a == b)
		{
			_min = _min < min_tree[a] ? _min : min_tree[a];
			_max = _max > max_tree[a] ? _max : max_tree[a];
		}

		cout << _min << " " << _max << endl;
	}
	return 0;
}

wgj2050 7년 전 1

저도 시간초과 났었는데 iostream 말고 cstdio로 바꿔서 scanf printf로 바꿔보세요

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

문제

문제

출처

ICPC

여기서 시간을 줄이고 싶은데 어떻게 해야 하나요.

sandrea 8년 전 0

wgj2050 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말