[백준OJ] 1306번 달려라 홍준

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

1306번: 달려라 홍준

---

 

풀이

세그먼트 트리를 이용해서 범위별 최댓값을 저장해둔뒤, 현재 홍준이가 뛰는 위치가 i번째( 단 M<=i && i<= N-M+1) 라고 한다면, 세그먼트트리의 쿼리를 이용하여 i-M ~ i+M 범위중 최댓값을 구해서 출력하면된다.

 

시간복잡도

세그먼트트리 초기화에 O(logN), 각 쿼리마다 O(logN) 이므로, 총 O(NlogN)이 된다.

 

코드

#include <iostream>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;

class Seg {
public:
	vector<int> arr;
	vector<ll> tree;
	Seg(int n) {
		arr.resize(n);
		int h = (int)ceil(log2(n));
		int tree_size = (1 << (h + 1));
		tree.resize(tree_size);
	}

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

	int init(int node, int st, int end) {
		if (st == end) {
			return tree[node]=arr[st];
		}

		int middle = (st + end) / 2;
		int left = init(node * 2, st, middle);
		int right = init(node * 2 + 1, middle + 1, end);
		return tree[node] = (left<right?right:left);
	}

	int query(int node, int st, int end, int l, int r) {
		if (r < st || end < l) {
			return -1;
		}
		if (l <= st && end <= r) {
			return tree[node];
		}

		int middle = (st + end) / 2;
		int left = query(node * 2, st, middle, l, r);
		int right=query(node * 2 + 1, middle + 1, end, l, r);

		return (left < right ? right : left);
	}
};


int main() {
	int n, m;
	cin >> n >> m;
	m--;
	Seg seg(n);
	seg.input(n);
	seg.init(1,0,n-1);
	for (int i = m; i < n - m; i++) {
		cout << seg.query(1, 0, n - 1, i - m, i + m) << " ";
	}
	return 0;
}