不用线段树、不用扫描线

#include <bits/stdc++.h>
using namespace std;

/*
分析：
1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16
1  2  3  5  7  9  12 14 16 19 22 23 24 25 28 29
11 11 11
   6  6  6
      13 13 13
				  7  7
					 3  3  3  3  3  3
						   18
								 13 13 13 13
									4  4
11 11 13 13 13 0  7  7  3  18 3  13 13 13 13 0
ans: 1 11 3 13 9 0 7 16 3 19 18 22 3 23 13 29 0
*/

const int N = 5000 + 5;

int a[N];
int b[N];
int h[N];
int t[2 * N]; // 离散化数组
int maxh[N];

int idd;
int idx;

int main()
{
	int x, c, y;
	while (scanf("%d%d%d", &x, &c, &y) != EOF) {
		a[++idd] = t[++idx] = x;
		h[idd] = c;
		b[idd] = t[++idx] = y;
	}

  // 离散化操作
	sort(t + 1, t + idx + 1);
	int m = unique(t + 1, t + idx + 1) - t - 1;
	
	for (int i = 1; i <= idd; i++) {
		a[i] = lower_bound(t + 1, t + m + 1, a[i]) - t;
		b[i] = lower_bound(t + 1, t + m + 1, b[i]) - t;
		for (int j = a[i]; j < b[i]; j++) {
			maxh[j] = max(maxh[j], h[i]);
		}
	}
	
//	for (int i = 1; i <= idx; i++) {
//		printf("%d ", maxh[i]);
//	}

  // 输出
	int now = 1;
	while (now <= idx) {
		printf("%d %d ", t[now], maxh[now]);
		while (now < idx && maxh[now] == maxh[now + 1]) {
			now++;
		}
		if (now <= idx) {
			now++;
		}
	}
	
	return 0;
}