11067번: Monotone Walkway

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

x값이 다른 두 점에 대해서는 x값이 작은 점들의 번호가 작아야 한다. x가 같은 점들의 번호 순서는, 해당 x값보다 작으면서 가장 큰 번호의 점을 찾고 이 번호의 y값을 시작으로 오름차순 혹은 내림차순 정렬해서 매기면 된다.

#include<cstdio>
#include<algorithm>
using namespace std;
int t, n, m, x;
pair<int, int> p[100001];
int main() {
    for (scanf("%d", &t); t--;) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d%d", &p[i].first, &p[i].second);
        sort(p + 1, p + 1 + n);
        for (int i = 1, e; i < n; i = e) {
            e = upper_bound(p + 1, p + 1 + n, make_pair(p[i].first, int(1e9))) - p;
            if (p[i].second^p[i - 1].second) reverse(p + i, p + e);
        }
        for (scanf("%d", &m); m--;) scanf("%d", &x), printf("%d %d\n", p[x].first, p[x].second);
    }
    return 0;
}