ABC 304

Table of Contents

D - A Piece of Cake

ピースの数は多いので愚直に全探索はできない。 イチゴが入るピースの数は少ないので各イチゴがどのピースに入るかという基準で考える。 イチゴが入るピースの右下の座標をそのピースの代表としてそのピースに入るイチゴの数を数えばよい。イチゴがどのピースに属するかはそのイチゴのすぐ右と下にある分割線を二分探索で探せば良い。

void solve() {
    ll W, H, N;
    cin >> W >> H >> N;

    vll p(N), q(N);
    rep(i, N) {
        cin >> p[i] >> q[i];
    }

    ll na;
    cin >> na;
    vll a(na + 1);
    rep(i, na) {
        cin >> a[i];
    }
    a.back() = W;

    ll nb;
    cin >> nb;
    vll b(nb + 1);
    rep(i, nb) {
        cin >> b[i];
    }
    b.back() = H;

    // イチゴが入るピースの右下の座標
    map<pair<ll, ll>, ll> cnt;
    rep(i, N) {
        ll rh, rw;
        rh = *lower_bound(all(a), p[i]);
        rw = *lower_bound(all(b), q[i]);

        cnt[{rh, rw}]++;
    }

    // ピースの数が最大数より少なかったらイチゴが 0 個のピースを sentinel
    // として一つ追加
    if ((ll)cnt.size() < (na + 1) * (nb + 1))
        cnt[{-1, -1}] = 0;

    ll maxv = 0, minv = INF;
    for (auto it = cnt.begin(); it != cnt.end(); it++) {
        chmin(minv, it->second);
        chmax(maxv, it->second);
    }
    cout << minv << ' ' << maxv << endl;
}