3163번: Falling Ants

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


$O(tn\lg n)$

왼쪽에 있는 개미부터 떨어지는 시각은 왼쪽으로 진행하는 개미가 다른 개미들을 무시하고 지나갔을 때 떨어지는 시각과 차례대로 대응된다. 오른쪽 방향에 대해서도 마찬가지이다.

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int MXN = 1e5;
int t, n, l, k;
pair<int, int> p[MXN];
int main() {
    for (scanf("%d", &t); t--;) {
        int c = 0;
        vector<int> v;
        scanf("%d%d%d", &n, &l, &k);
        for (int i = 0, x; i < n; i++) {
            scanf("%d%d", &x, &p[i].second);
            if (p[i].second < 0) p[c++].first = x;
            else v.push_back(l - x);
        }
        for (int it : v) p[c++].first = it;
        sort(p, p + n);
        printf("%d\n", p[k - 1].second);
    }
    return 0;
}