[BaekJoon][3020] 개똥벌레

BAEKJOON ONLINE JUDGE

3020 개똥벌레

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

#include <cstdio>
#include <algorithm>
using namespace std;
 
int n, h;
int bottom[100100], top[100100];
int cut[500001];
 
int bsearch(int num)
{
    int s = 0, e = n / 2 - 1;
    int m;
    int ans;
 
    while (s <= e) {
        m = (s + e) / 2;
 
        if (bottom[m] < num)    s = m + 1;
        else                    e = m - 1;
    }
 
    ans = n / 2 - e - 1;
 
    s = 0, e = n / 2 - 1;
    while (s <= e) {
        m = (s + e) / 2;
 
        if (top[m] < h - num + 1)       s = m + 1;
        else                            e = m - 1;
    }
 
    ans += n / 2 - e - 1;
    return ans;
}
 
int cutbsearch(int num)
{
    int s = 1, e = h;
    int m;
 
    while (s <= e) {
        m = (s + e) / 2;
 
        if (cut[m] < num)       s = m + 1;
        else                    e = m - 1;
    }
 
    return e;
}
 
int main()
{
    int i;
    int num;
 
    scanf("%d %d", &n, &h);
 
    for (i = 0; i < n; i++) {
        scanf("%d", &num);
 
        if (i % 2)    top[i / 2] = num;
        else          bottom[i / 2] = num;
    }
 
    sort(bottom, bottom + n / 2);
    sort(top, top + n / 2);
 
    for (i = 1; i <= h; i++) {
        cut[i] = bsearch(i);
    }
    sort(cut + 1, cut + h + 1);
 
    printf("%d %d\n", cut[1], cutbsearch(cut[1] + 1));
 
    return 0;
}