BOJ 13334 철로

Source.cpp

#include <stdio.h>
#include <vector>
#include <algorithm>

int main()
{
	int n, d, input[100000][2], cursor = -100000001, answer = 0;
	std::vector<int> st, ed;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) scanf("%d %d", &input[i][0], &input[i][1]);
	scanf("%d", &d);
	for (int i = 0; i < n; i++)
	{
		if (std::abs(input[i][1] - input[i][0]) > d) continue;
		st.push_back(std::min(input[i][0], input[i][1]));
		ed.push_back(std::max(input[i][0], input[i][1]));
	}
	std::sort(st.begin(), st.end());
	std::sort(ed.begin(), ed.end());
	for (int i = 0; i < st.size(); i++)
	{
		if (st[i] == cursor) continue;
		cursor = st[i];
		int temp;
		temp = st.end() - std::lower_bound(st.begin(), st.end(), cursor);
		temp += std::upper_bound(ed.begin(), ed.end(), cursor + d) - ed.begin();
		temp -= st.size();
		if (temp > answer) answer = temp;
	}
	printf("%d\n", answer);
	return 0;
}