AOJ 0564: Bug Party

AOJ で解いた問題の中で 300 問目にあたる問題です.
セグメント木と二分探索を用いました.

N匹の微生物たちについて, foo許容量が多い微生物をシャーレに入れていき, それらの微生物のfoo放出量の総和が, もっとも(foo許容量が小さい微生物) * N より小さければ, すべての微生物が死なずにシャーレの中に入ることになります.
このNを求めるために二分探索をし, 具体的な操作はセグメント木を用います. 2つを併せて, オーダーはO(N log^2 N)くらいです.

セグメント木は、数値の更新が更新が頻繁に行われるデータ列の中の最大値を求めるものを構築しました.
更新をO(log N), 取り出しをO(1)で出来るような構造にしました. (これだけなら別のデータ構造でもいいかもしれないですが...)
自由自在にセグメント木を扱えるようにしていきたいです.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef long long ll;
typedef struct {
    ll a, b;
} BUG;

BUG foo[300000];
int n;

int seg[1 << 19][2];
int seg_size;

ll _max(ll a, ll b)
{
    return (a > b ? a : b);
}

void init(int n)
{
    seg_size = 1;
    
    while (n > seg_size){
        seg_size *= 2;
    }
    memset(seg, -1, sizeof(seg));
}

void update(int k, int x)
{
    k += seg_size;
    
    seg[k][0] = x;
    seg[k][1] = k - seg_size;
    
    while (k != 0){
        k = (k - 1) / 2;
        if (seg[k * 2 + 1][0] > seg[k * 2 + 2][0]){
            seg[k][0] = seg[k * 2 + 1][0];
            seg[k][1] = seg[k * 2 + 1][1];
        }
        else {
            seg[k][0] = seg[k * 2 + 2][0];
            seg[k][1] = seg[k * 2 + 2][1];
        }
    }
}

int comp(const void *a, const void *b)
{
    BUG x, y;
    x = *(BUG *)a;
    y = *(BUG *)b;
    
    if (x.b != y.b){
        return (y.b - x.b);
    }
    else {
        return (x.a - y.a);
    }
}

int canPut(int piv)
{
    int i;
    ll lim;
    
    init(piv);
    
    lim = 0;
    for (i = 0; i < piv - 1; i++){
        lim += foo[i].a;
        update(i, foo[i].a);
    }
    
    while (i < n){
        if (i == piv - 1){
            lim += foo[i].a;
            update(i, foo[i].a);
        }
        else {
            lim -= seg[0][0];
            lim += foo[i].a;
            update(seg[0][1], foo[i].a);
        }
        
        if (lim <= foo[i].b * piv){
            return (1);
        }
        i++;
    }
    
    return (0);
}

int main(void)
{
    int i;
    int left, right, center;
    
    scanf("%d", &n);
    
    for (i = 0; i < n; i++){
        scanf("%lld %lld", &foo[i].a, &foo[i].b);
    }
    
    left = 0;
    right = n;
    
    qsort(foo, n, sizeof(BUG), comp);
    
    while (left != right){
        center = (left + right + 1) / 2;
        
        if (canPut(center)){
            left = center;
        }
        else {
            right = center - 1;
        }
    }
    
    printf("%d\n", left);
    
    return (0);
}