[KOI]전국본선 2014 중등부 세번째 문제

#include <stdio.h>
#include <algorithm>
#include <deque>
using namespace std;

const int MAX_SIZE = 500000;

struct BUS{
	int s, e, index;
};

bool comp(BUS a, BUS b) {
	return (a.s == b.s) ? (a.e > b.e) : (a.s < b.s);
}

bool comp1(BUS a, BUS b) {
	return (a.index < b.index);
}

BUS bus[MAX_SIZE];

int main()
{
	int N, M, end_point = 0;
	scanf("%d %d", &N, &M);
	for(int i = 0; i < M; ++i){
		scanf("%d %d", &bus[i].s, &bus[i].e);
		bus[i].index = i + 1;

		if (bus[i].s > bus[i].e) {
			end_point = max(end_point, bus[i].e);
			bus[i].e += N;
		}
	}

	sort(bus, bus + M, comp);

	deque<BUS> q;
	for (int i = 0; i < M; ++i) {
		if (q.empty() || q.back().e < bus[i].e) {
			q.push_back(bus[i]);
		}
	}

	while (!q.empty() && q.front().e <= end_point) {
		q.pop_front();
	}

	sort(q.begin(), q.end(), comp1);

	for (auto x : q) {
		printf("%d ", x.index);
	}

	return 0;
}