2016年2月1日 星期一

[IOI Camp Judge]農田分配 (題目備份)

IOI Camp Judge是暫時性的,因此在這裡作個題目備份,請大家參考~
題解在這裡

農田分配

Time Limit: 8s

Description

米提爾是個大地主,擁有  塊農地,這些農地由左而右排成一直線,我們依序將這些農地由左至右編號為 
米提爾擁有  個助手來幫助他管理他的農地,每塊農地都會有恰好一個助手管理。米提爾對他的助手非常友善,因此他建立了一個加薪機制,每個助手有著自己的積分,一開始大家的積分都是 ,只要積分達到某個標準,助手便可以加薪。基於米提爾對每個助手的喜愛感不盡相同,每個助手所要達到的標準也不一定相同。
但米提爾該如何設計累積積分的方法呢?聰明的他設計了一台機器人,機器人每次會對一個區間  的農地進行拍一張照片,一共拍攝  張,米提爾在得到這些照片後,會一一看過,並根據照片給予一些助手積分,對於第  張照片,米提爾會給予出現在這張照片農地的管理者都增加  的積分,如果某個助手在裡面出現了多次,那個助手並不會因此多得到積分,仍然是得到  的積分。
身為有加薪機會的助手,當然很好奇自己到底能不能加到薪,現在他們都想問你,在米提爾看到哪一張照片時可以達到自己的積分標準。

Input Format

第一行有一個正整數 ,代表總共有幾筆測試資料。
每筆測試資料第一行有兩個以空白隔開的正整數  與 ,表示有  個助手與  塊農地。
第二行有  個正整數 ,第  個數字為第  個助手的積分標準。
第三行有  個正整數 ,第  個數字為管理第  塊農地的助手,我們並不保證每個助手都會有管理的農地。
第四行有一個正整數 ,表示米提爾設計的機器人照了  張照片。
接著有  行,每行三個正整數 ,表示第  張照片所照到的農地範圍,以及管理這些農地的助手分別可獲得  的積分。
  • 對於所有測試資料,我們保證不超過  筆測試資料滿足 

Output Format

對於每筆測試資料,請輸出  個整數於一行,第  個數字表示第  個助手可以在哪一張照片時達到他的標準,若無法達到標準請輸出 

Sample Input

1
3 5
10 12 5
1 2 2 3 1
3
1 4 5
2 5 3
2 4 4

Sample Output

-1 3 1

Hint

  • 在第一張照片時,三個助手的積分依序為 
  • 在第二張照片時,三個助手的積分依序為 
  • 在第三張照片時,三個助手的積分依序為 

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原