種子論壇 | 高雄市資訊培育協會學員討論區

標題: 2025成大初賽_PaParty [打印本頁]

作者: may 時間: 2025-4-18 12:06 標題: 2025成大初賽_PaParty

PaParty
問題敘述
pA 身為大家賽中通常第一道看到的題目，祝福各位參賽者都能像參加Party一樣開
心的享受這場比賽。
然而對於I人睿高來講，參加如Party這種的大型社交場合，卻不一定是件享受的
事。過多的社交互動會使他感到疲憊，甚至是有些壓力；但若完全避免社交，又會讓他
感到孤單與疏離，在適當的時刻與他人交流，並從中獲得正向的能量，則是最完美的狀
態。這就像在比賽中找到自己的節奏一樣，既不急躁也不退縮，才能真正享受過程。
如今睿高打算參加「敗大寒期大專生城市設籍邀請派對」，他知道這個派對總共舉辦
n 天，且有k個人會參加，以及那k個人的社恐（社交恐怖）值a和他們參加哪幾天派
對的區間l, r（包含第l與r天）。
恐懼源自於火力不足。社恐值低於自身社交力的人是不會帶來恐懼的。睿高預測他
未來可能會有q種社交力S，而對於每一天，派對中的每個人只要社恐值a超過睿高的
社交力，都會消耗掉睿高的承受力a。
請幫他計算出對於q種可能的S，睿高在一開始時至少需要多少承受力，才能使最
後承受力不被耗至負數的前提下參加完這n天派對，並將這q次最低承受力需求取和，
輸出其對109+7取模後的結果。
輸入說明
第一行有兩正整數n,k。
接下來有k行，第i行代表第i個人的社恐值a，以及他會出現的天數區間l,r。
再來一行有一個正整數q。
然後還有q行，代表睿高希望你計算的q種社交力S。
輸出說明
對於每筆詢問，依序輸出一行，表示答案。
測資限制
1
•1≤n≤5×105
•1≤k≤2×105
•1≤a≤108
•1≤l≤r≤n
•1≤q≤2×105
•1≤S≤108
範例測資
範例輸入1
103
123
246
369
3
1
2
3
範例輸出1
30
當S為1時，最低所需的承受力是2×(6−4+1)+3×(9−6+1)=18
當S為2時，最低所需的承受力是3×(9−6+1)=12
當S為3時，沒有人的社恐值大於3，最低所需的承受力是0
所以答案就是(18+12) mod109+7=30
2

歡迎光臨種子論壇 | 高雄市資訊培育協會學員討論區 (http://seed.istak.org.tw/)