Kodaman コンテスト:K - Customers
問題
https://www.hackerrank.com/contests/kodamanwithothers/challenges/k-customers-2
解法
一つ目のクエリは,各お客さんの入店・出店時刻を独立に考えることが出来るから,X と Y を昇順にソートしておき,std::upper_bound() を用いることで簡単に人数を求めることが出来る.各クエリ O(logN).
二つ目のクエリに関して,まず,各時間に店内にいるお客さんの数を数える.これは,0 ~ H で配列を持って置き,入店時の時刻に +1,出店時の時刻に -1 して前から累積和を取ることで簡単に計算できる.次に,std::map などを用いて客数ごとにその客数であった時刻を配列に集めていく.これを std::vector などに移し替えて,客数の多い順にソートしておくことで,各クエリに O(1) で対応できる.
全体で O(AlogN + HlogH + B).
解答