Problem : 351 - E. 小紫愛網拍
Problem Statistics
Solved Member:
4 Submission:
45 User Tried:
11 Statement:
小紫是個有點害羞的平凡高中生，他平常在家喜歡兼職做網拍。
我也不知道為什麼，小紫決定要賣置物櫃。採買過家具的人就知道，買之前一定要先量一下自己預定的位子放的放不下那個東西，還有門的寬與高也要事先量好，不然如果買過來發現卡在門外或是沒地方放就悲劇了。為了因應各個顧客的需求，小紫所賣的置物櫃有很多種型號，每個型號都有他的寬度與高度，而且包含的範圍非常大，以求各種不同需求的顧客都能買到他心目中的最佳櫃子。
你可以假設所有顧客都是聰明且貪婪的。他們總是希望在家裡塞得下的前提下買盡可能大的櫃子。「盡可能大」的定義為盡可能買在寬度限制下最寬的櫃子，如果有很多個櫃子同樣是最寬的，那麼就買高度最高的那一個，如果還是有很多種可能，那麼就輸出編號最小的。今天給你每種型號的櫃子的長度和寬度，以及你每一位顧客需求的寬度和高度，你可以幫每位顧客找到他心目中的最佳型號嗎?
Input:Output:
第一行有一個整數n，表示小紫所販賣的櫃子的型號數量。
接下來n行，每行有兩個整數wi、hi，依序為型號1, 2, 3,……, n的寬度與高度
再下一行 有一個整數q，表示有興趣想買櫃子的顧客的數量。
接下來q行，每行有兩個整數aj、bj，分別表示第j個顧客需求的寬度與高度。
對每個顧客，請輸入一個整數x，表示最適合該顧客的型號，如果沒有任何符合要求的型號，那麼就輸出”-1”(不含引號)。
Sample Input:Sample Output:
#Case1
3
1 5
3 4
3 3
2
3 5
2 2
#Case2
3
3 3
3 4
3 5
1
3 4
#Case3
1
4 3
1
3 4
2
-1
2
-1
HINT:
20% 1 <= n <= 1,000、1 <= q <= 1,000、wi, ai = 1、1 <= hi, bj <= 1,000,000,000
20% 1 <= n <= 1,000、1 <= wi, hi, aj, bj <= 1,000,000,000
20% 1 <= n, q <= 500,000、wi, ai = 1、1 <= hi, bj <= 1,000,000,000
100% 1 <= n, q <= 500,000、1 <= wi, hi, aj, bj <= 1,000,000,000
Source:
2014 延平校內賽
Problem Setter
rilak Testdata:
| Test | Time | Memory | Score |
|---|
| 0-1 | 1000ms | 262144kb | |
| 0-2 | 1000ms | 262144kb | |
| 0-3 | 1000ms | 262144kb | |
| 1 | 1000ms | 262144kb | 20 |
| 2 | 1000ms | 262144kb | 20 |
| 3 | 5000ms | 262144kb | 20 |
| 4 | 5000ms | 262144kb | 20 |
| 5 | 5000ms | 262144kb | 20 |