BOJ 10165 - 버스노선 ( KOI 고, 라인스위핑 )

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

 

m^2 이하의 논리가 생각나지 않아서 풀이를 찾아봤던 문제..ㅜㅜ 

 

https://milkclouds.github.io/2019/02/09/BOJ-10165-%EB%B2%84%EC%8A%A4-%EB%85%B8%EC%84%A0/

이 글을 참고했습니다. 감사합니다... 

reg in reg, reg in irreg, irreg in irreg으로 상황을 나누셨던데, 이 상황들의 합집합이 모든 상황을 나타내면서 교집합이 없다...

 

regular in regular의 상황일때 논리가 인상깊다.

[a,b]를 a는 오름차순, b는 내림차순으로 정렬하고 순서대로 처리하면, 현재 보고 있는 노선의 end가 여태 나온 end의 최대갑인 lastEnd보다 작으면 반드시 어떤 노선에 포함될 수 밖에 없다. (현재 보고있는 노선의 start는 lastEnd의 주인인 노선의 start보다 항상 크기 때문이다.)

 

#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;
typedef pair<int, int> P;
typedef pair<P, int> LN; //노선 자료형. [a,b],idx
const int INF = 1e9;

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

	int n, m; cin >> n >> m;

	vector<LN> line;
	int irrA = INF, irrB = 0;
	for (int i = 0,a,b; i < m; i++) {
		cin >> a >> b;
		if (a > b) {
			irrA = min(irrA, a);
			irrB = max(irrB, b);
		}
		line.push_back({ {a,b},i+1 });
	}

	sort(line.begin(), line.end(), [](LN ln1, LN ln2) {
		if (ln1.first.first == ln2.first.first)
			return ln1.first.second > ln2.first.second;
		else 
			return ln1.first.first < ln2.first.first;
	});

	bool flag[500001] = { 0 }; //flag == 0 이면 출력할 것
	int lastEnd = 0;
	for (int i = 0; i < m; i++) {
		int st = line[i].first.first, en = line[i].first.second;
		int idx = line[i].second;
		if (st > en) continue;

		//regular in regular
		if (lastEnd >= en) flag[idx] = true;
		else lastEnd = en;

		//regular in irregular
		if (irrA <= st || en <= irrB) flag[idx] = true;
	}

	//irregular in irregular
	lastEnd = 0;
	for (int i = 0; i < m; i++) {
		int st = line[i].first.first, en = line[i].first.second;
		int idx = line[i].second;
		if (st < en) continue;
		en += n;
		
		if (lastEnd >= en) flag[idx] = true;
		else lastEnd = en;
	}

	for (int i = 1; i <= m; i++) if (!flag[i]) cout << i << " ";
}