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 |