[백준/BOJ] 백준 8201번 : Pilots

https://www.acmicpc.net/problem/8201

8201번: Pilots

구간의 최댓값을 저장하는 세그먼트 트리와, 구간의 최솟값을 저장하는 세그먼트를 만들고, 구간의 최댓값과 최솟값을 동시에 반환하는 세그먼트 트리의 쿼리를 만들어 투 포인터를 이용해 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;

int t, n;
vector<int> a;
vector<int> max_sgmtt(3000000 * 4);
vector<int> min_sgmtt(3000000 * 4);

int MakeMinSgmtt(int here, int range_left, int range_right)
{
	if (range_left == range_right)
		return min_sgmtt[here] = a[range_left];

	int left_child = here * 2 + 1;
	int right_child = here * 2 + 2;
	int range_mid = (range_left + range_right) / 2;

	return min_sgmtt[here] = min(MakeMinSgmtt(left_child, range_left, range_mid), MakeMinSgmtt(right_child, range_mid + 1, range_right));
}

int MakeMaxSgmtt(int here, int range_left, int range_right)
{
	if (range_left == range_right)
		return max_sgmtt[here] = a[range_left];

	int left_child = here * 2 + 1;
	int right_child = here * 2 + 2;
	int range_mid = (range_left + range_right) / 2;

	return max_sgmtt[here] = max(MakeMaxSgmtt(left_child, range_left, range_mid), MakeMaxSgmtt(right_child, range_mid + 1, range_right));
}

//해당 구간의 최댓값과 최솟값 반환
pair<int, int> QuerySgmtt(int here, int range_left, int range_right, int find_left, int find_right)
{
	if (find_left <= range_left && range_right <= find_right)
		return make_pair(max_sgmtt[here], min_sgmtt[here]);

	if (find_right < range_left || range_right < find_left)
		return make_pair(-1, 2000000001);

	int left_child = here * 2 + 1;
	int right_child = here * 2 + 2;
	int range_mid = (range_left + range_right) / 2;

	pair<int, int> query1 = QuerySgmtt(left_child, range_left, range_mid, find_left, find_right);
	pair<int, int> query2 = QuerySgmtt(right_child, range_mid + 1, range_right, find_left, find_right);
	return make_pair(max(query1.first, query2.first), min(query1.second, query2.second));
}

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

	cin >> t >> n;

	for (int i = 0; i < n; i++)
	{
		int input;
		cin >> input;

		a.push_back(input);
	}

	MakeMinSgmtt(0, 0, n - 1);
	MakeMaxSgmtt(0, 0, n - 1);

	//투포인터를 이용
	int left = 0;
	int right = 0;
	int result = 0;

	while (1)
	{
		if (right >= a.size())
			break;

		pair<int, int> this_check = QuerySgmtt(0, 0, n - 1, left, right);

		//조건을 만족할때
		if (this_check.first - this_check.second <= t)
		{
			result = max(result, right - left + 1); //left~right구간은 조건을 만족한다
			right++;
		}

		else
		{
			left++;
		}
	}

	cout << result;

	return 0;
}