略譯

原題目連結

給你 n 筆資料，每筆告訴你工廠名、出產過車子最低和最高價格，
共有 q 組詢問，每組給你一個整數 p，
輸出出產車子價格區間包含 p 的工廠名，
如果有多間同時符合或沒有半間符合，輸出 UNDETERMINED

題解

照題目敘述暴力硬幹即可。

原本至多 10000 間的工廠，面對至多 1000 組詢問，
nq 的複雜度運算量高達 1000 萬，應該是難以 AC 的，
但實際測資十分小，暴力解跑得相當快。

試著壓複雜度，反而因為常數大而變慢了…

一個加速方式是對所有工廠排序，
可以透過二分搜尋快速地找到最低價格符合的一組，
並且在找到最低價格不符時就可以結束了，因為後面只會更大。

但在極端測資下，複雜度不見得壓得下來。

理想的做法是實作線段樹，
將每個工廠看成數線上的一條線段，就能知道每一個價格被幾個線段覆蓋。

線段樹可以在 n log n 的建表之後，對每組詢問以 log n 的複雜度回答。
實際複雜度 n log n + q log n

實作提示

• 可以在找到兩組符合條件時，就直接回答，並且不再繼續找。