AtCoder ABC 304 D - A Piece of Cake をイベントソートで解く(C++, Python)

適当な入寮が与えられたときにケーキを図示すると以下のようになります。赤丸をいちご、赤い太線をカットの位置とします。

ピースを考える際、$x$, $y$の細かい座標は必要なく、カットされる線分との関係だけを気にすればよいです。これを図示します。

縦方向のカットで分割されたピースたちを$partition$とし、その中で横方向のカットで分割されたピースを$group$と呼ぶことにします。

$x$を時間だと考えます。各いちご$(x,y)$は時間$x$に$y$の位置にイチゴが追加されると考えます。
カットのイベントは各$partition$を分割するイベントで発生するのは配列$a$及び($a$には含まれない)ケーキの右端の時間に発生します。

これらを次のように以下の２種類のイベントで表現します。

time, 0, None: カットイベント。今パーティションに存在するグループの各min, maxを数える
time, 1, y: yが所属するグループにイチゴを追加する。

実装を考えます。

• イベントは入力から生成できます。それをソートして順にみることで左から右に処理できます。
• $y$から$group$は何本のカットを超えたgroupか？であるのでlower_bound(bisect_left)により高速に求められます。
• $a, b \leq 2\cdot 10^{5}$ であるので、各partitionごとにmin, maxを求めるために全groupを見ると$ab$の時間がかかり間に合いません。各partion内ではmap(default_dict)など、存在するgroupの要素だけを数えます。これにより$N$だけを数えれば良くなります。

実装(Python)

from collections import defaultdict
"""
event (x, 0, None) x でカットされた。今を清算する
event (x, 1, y ) yの座標に置かれる
"""
ansmax , ansmin = -1, 10**9
ox, oy = map(int, input().split())
n = int(input())
event = [] # イベント
for _ in range(n):
    x, y = map(int, input().split())
    event.append( (x, 1, y) ) # event1を追加
xcutcnt = int(input())
cutx = list(map(int, input().split()))
ycutcnt = int(input())
cuty = list(map(int, input().split()))
cutx.append(ox) # 最後のカット
for x in cutx: event.append( (x, 0, None) ) # event0を追加
event.sort() #イベントソート
cnt = defaultdict(int)
from bisect import bisect_left
for x, t, y in event:
    if t == 0:
        buf = []
        for k in cnt.keys(): buf.append(cnt[k])
        buf.sort() # そのpartitionをソートする。min, maxがわかる。
        cnt = defaultdict(int)
        if len(buf) == 0: continue # このpartionに載っているpieceが存在しない
        ansmax = max(ansmax, buf[-1]) # 最大候補
        # 最小: このパーティションのgroupの数が yの切る数+1 未満なら"0"のピースがになり確定
        #      そうでない場合は[0]が最小の候補になる
        if len(buf) < (ycutcnt + 1): ansmin = min(ansmin, 0)
        else: ansmin = min(ansmin, buf[0])
    elif t == 1:
        # 乗せるyから++するgroupの番号を得て ++する
        ind = bisect_left(cuty, y) # 乗せるgroup番号を二分探索
        cnt[ind] += 1
print(ansmin, ansmax)

実装(C++)

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define REP(i, n) FOR(i,0,n)
int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    int ansmax = -1, ansmin = 1<<30;
    int ox, oh; cin >> ox >> oh;
    int n; cin >> n;
    vector<pair<int, int>> event;
    REP(i, n){
        int x, y; cin >> x >> y;
        event.push_back({x, y});
    }
    int xcutcnt, ycutcnt;
    cin >> xcutcnt;
    vector<int> cutx(xcutcnt);
    REP(i, xcutcnt) cin >> cutx.at(i);
    cin >> ycutcnt;
    vector<int> cuty(ycutcnt);
    REP(i, ycutcnt) cin >> cuty.at(i);
    cutx.push_back(ox);
    for(auto x: cutx) event.push_back({x, -1});
    sort(event.begin(), event.end());
    map<int, int> cnt;
    for(auto &p: event){
        if(p.second != -1){
            auto it = lower_bound(cuty.begin(), cuty.end(), p.second);
            auto ind = distance(cuty.begin(), it);
            ++cnt[ind];
        } else {
            vector<int> buf;
            for(auto &[k, v]: cnt) buf.push_back(v);
            sort(buf.begin(), buf.end());
            cnt.clear();
            if(buf.size() == 0) continue;
            ansmax = max(ansmax, buf.at(buf.size()-1));
            if(buf.size() <= ycutcnt) ansmin = 0;
            else ansmin = min(ansmin, buf.at(0));
        }
    }
    cout << ansmin << " " << ansmax << "\n";
}