백준 3163: 떨어지는 개미 [C언어]

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

3163번: 떨어지는 개미

 

#include <stdio.h>
int T, N, L, K;
int p[1000001];
int id[1000001]; int front, rear;
int plus[1000001]; int pn, pp;
int minus[1000001]; int mn, mp;
void merge(int data[], int p, int q, int r) {
    int i = p, j = q+1, k = p;
    int tmp[1000001]; 
    while(i<=q && j<=r) {
        if(data[i] <= data[j]) tmp[k++] = data[i++];
        else tmp[k++] = data[j++];
    }
    while(i<=q) tmp[k++] = data[i++];
    while(j<=r) tmp[k++] = data[j++];
    for(int a = p; a<=r; a++) data[a] = tmp[a];
}
void mergeSort(int data[], int p, int r) {
    int q;
    if(p<r) {
        q = (p+r)/2;
        mergeSort(data, p , q);
        mergeSort(data, q+1, r);
        merge(data, p, q, r);
    }
}
void input(){
    for (int i = 0; i < 1000001; i++) {
        plus[i] = 5000001; minus[i] = 5000001;
    }
    front = 0; rear = 0; pn = 0; pp = 0; mn = 0; mp = 0;
    scanf("%d %d %d", &N, &L, &K);
    for (int i = 0; i < N; i++) {
        scanf("%d %d", p + i, id + i);
        if (id[i] > 0) plus[pn++] = L - p[i];
        else minus[mn++] = p[i];
    }
}
void ad_hoc(){
    mergeSort(plus, 0, pn - 1); mergeSort(minus, 0, mn - 1);
    rear = N - 1;
    int print;
    for (int i = 0; i < K; i++) {
        if (plus[pp] < minus[mp]) {
            pp++;
            rear--;
            print = 1;
        }
        else if (plus[pp] == minus[mp]) {
            if (id[front] < id[rear]) {
                mp++;
                front++;
                print = 0;
            }
            else {
                pp++;
                rear--;
                print = 1;
            }
        }
        else {
            mp++;
            front++;
            print = 0;
        }
    }
    printf("%d\n", print ? id[rear + 1] : id[front - 1]);
}
int main(){
    scanf("%d", &T);
    while (T--) {
        input();
        ad_hoc();
    }
}