(백준 2357번 최솟값과 최댓값 C++) 라이님 블로그 대회 알고리즘 따라잡기 12) SegmentTree 3

세그먼트 트리랑 친해지는 중🌚

 

백준 2537번

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

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
constexpr int MAX = 1000000001;
constexpr int MIN = -1;

pair<int, int> pairsum(pair<int, int> p1, pair<int, int> p2) {
	int first = min(p1.first, p2.first);
	int second = max(p1.second, p2.second);
	pair<int, int> p3 = { first, second };
	return p3;
}
struct segTree {
	int n, start;
	vector<pair<int, int>> v;

	segTree(int n) : n(n) {
		start = 1;
		while (start < n) start *= 2;
		v.resize(2 * start);
	}

	void construct() {
		for (int i = start - 1; i > 0; i--) {
			v[i].first = min(v[i * 2].first, v[i * 2 + 1].first);
			v[i].second = max(v[i * 2].second, v[i * 2 + 1].second);
		}
	}

	void minmax(int a, int b) {
		pair<int, int> p = minmax(a, b, 1, 0, start);
		cout << p.first << " " << p.second << "\n";
	}
	pair<int, int> minmax(int a, int b, int node, int na, int nb) {
		if (nb <= a || b <= na) return { MAX, MIN };
		if (a <= na && nb <= b) return v[node];
		int mid = (na + nb) / 2;
		return pairsum(minmax(a, b, node * 2, na, mid), minmax(a, b, node * 2 + 1, mid, nb));
	}
};
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N, M; cin >> N >> M;
	segTree st(N);

	for (int i = st.start; i < st.start + N; i++) {
		int temp; cin >> temp;
		st.v[i] = make_pair(temp, temp);
	}

	st.construct();

	for (int i = 0; i < M; i++) {
		int a, b; cin >> a >> b;
		st.minmax(a-1, b);
	}
	return 0;
}

 

 

💥시간초과가 났던 이유는 endl 때문이었따!!!!

endl이 속도가 오래 걸리는 건 알았는데 이것때문에 시간 초과라니..ㄷㄷ

 

endl 을 "\n"으로 바꿔주니 바로 정답!

 

https://www.acmicpc.net/board/view/95135

⬅️ 이 분 덕분에 알게되었따리!!!!