Google Code Jam 2019 Round 1B A. Manhattan Crepe Cart

問題

グリッドがあり、各交差点は0からQまでの番号の組で表現できる。
今、P人の人が交差点に立っており、それぞれ、東西南北のいずれか一方を向いている。
各人は、向いている向きの方向に1交差点進んだ領域のどこかの交差点に用事があることがわかっている。(例えば、(Xi,Yi)で北を向いている場合は、北をy軸の正方向とすると、y>Yiとなる領域の交差点のどこかに用事がある)

今、各人の用事がある可能性がある領域で一番人数が多い交差点を見つけたい。
ただし、同じ人数の場合は、一番南西にある交差点を答えよ。

制約

• 1 <= T <= 100
• 1 <= P <= 500
• 20秒以内
• Q = 10^5

解法

2次元領域だが、各軸は独立に考えることができる。
なので、各軸についてimos法などで範囲更新して、一番数が多いところを見つける。
あとは、それぞれの数が多いところの和が2次元領域でも一番数が多いところになっているので、そのなかでも一番南西となる地点を答えればよい。