2016年2月25日 星期四

[HOJ 282]Empire disruption (題目備份)

HOJ生病惹QQ,因此在此悼念昔日光彩
題目備份,請參考~
題解在這裡
敬告:目前HOJ主機也許進入瀕死狀態了,常常無預警跳電。請看到這則公告的人能注意備份自己的資料,感謝。
至於主機壞掉以後會如何目前並沒有任何規劃.. 
Submit  Ranklist

Problem : 282 - Empire disruption

Problem Statistics
Solved Member: 13  Submission: 29  User Tried: 18
Problem:
瀚瀚國一共有 m 個城市,這 m 個城市排列成一條線,依序編號為 1,2,3,...,m。

但是最近瀚瀚國發生政變,瀚瀚國國王瀚瀚非常困擾,m 個城市當中只剩下 n 個城市在瀚瀚的控制範圍內。

為此,瀚瀚決定對其他的城市實行痴漢(?)式清略,他準備了 q 種計畫,每一種計畫用兩個整數 x,y 來表示。每次侵略會以每一個控制的城市為中心,以每個城市 a 為中心去攻打並佔領編號 a-x, a-x+1, a-x+2,..., a-1, a, a+1, a+2,..., a+y 的城市(若存在的話)。

但是由於計畫數量太多了,他想知道每一種計畫執行結束之後,他所佔領的城市數量會有多少個。請你幫他算算看吧!




例如 m=7,而瀚瀚的控制範圍為 2,4 兩個城市。

對於計畫 x=3, y=4,則編號 2 的城市會去佔領 1~6 之間的城市,而編號 4 的城市則會去佔領 1~7 之間的城市。因此計畫結束之後瀚瀚佔領了總共 7 個城市。

而對於計畫 x=3, y=0,編號 2 的城市會去佔領 1~2 之間的城市,而編號 4 的城市則會去佔領 1~4 之間的城市。因此計畫結束之後瀚瀚佔領了總共 4 個城市。
Input:
每一筆輸入的第一行會有三個整數,m, n, q,依序代表總城市數量、瀚瀚控制的城市數量、以及計畫數量。

第二行會有 n 個整數 a1, a2, ..., an,分別代表瀚瀚控制的城市編號。每個數字皆相異,並且由小到大排列。

接下來的 q 行,每一行會有兩個數字 x,y ,依序代表每一個計畫的敘述。



限制:
1 ≤ m ≤ 1000000000
1 ≤ n ≤ min(m, 100000)
1 ≤ q ≤ 100000
0 ≤ x,y ≤ 1000000000

對於其中 20% 的測試資料滿足: n ≤ 300,m,q ≤ 1000
對於其中 50% 的測試資料滿足: n,q ≤ 2000
Output:
請輸出 q 行,每行一個數字。代表每一個計畫執行之後,瀚瀚會佔領的城市數量。
Sample Input:
SAMPLE A:
7 2 3
2 4
1 1
3 0
3 4

SAMPLE B:
100 5 5
3 18 24 57 90
1 8
27 0
15 16
22 3
2 2
Sample Output:
SAMPLE A:
5
4
7

SAMPLE B:
46
80
98
79
25
HINT:
敘述中的範例與 SAMPLE A 的其中兩筆詢問是相同的
Problem Setter
Nekosyndrome
Testdata:
TestTimeMemoryScore
0-12500ms131072kb
0-22500ms131072kb
12500ms131072kb10
22500ms131072kb10
32500ms131072kb10
42500ms131072kb10
52500ms131072kb10
62500ms131072kb10
72500ms131072kb10
82500ms131072kb10
92500ms131072kb10
102500ms131072kb10

沒有留言:

張貼留言

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