2319 . 貓咪與老鼠
TopCoder
Tags
Description
老鼠是個天才兒童，在三歲時養了一隻貓咪。
貓咪每天都會給老鼠 1kg 的起司，只是今天老鼠把起司放在磅秤上後，發現起司竟然少了 24g。
於是老鼠給了貓咪一個池塘，池塘裡有 $n$ 隻魚，編號為 $1\sim n$，編號 $i$（$1\leq i\leq n$） 的魚大小為 $a_i$。
每隻魚的視力都不相同，能看到的範圍也各有差異，具體來說，編號 $i$ 的魚的可視範圍為 $[l_i,r_i]$，代表這隻魚可以看到編號 $l_i\sim r_i$ 的魚。
如果編號 $i$ 的魚的可視範圍內，有魚的大小比自己大，那牠就會太過自卑而翻白肚，也就是說，只要存在一個 $j$，滿足 $l_i\leq j\leq r_i$，且 $a_j>a_i$，那編號 $i$ 的魚就會翻白肚。
為了不讓任何一隻魚翻白肚，貓咪可以事先餵池塘裡的魚飼料，編號 $i$ 的魚吃了 $1$ 粒飼料後會讓 $a_i$ 增加 $1$，也就是大小會變大 $1$。
因為貓咪的池塘很大，一隻魚可以吃任意多粒的飼料。只是因為飼料很貴，貓咪想要使用盡量少粒的飼料，使得池塘裡沒有任何一隻魚翻白肚。
請幫幫貓咪計算最少要使用幾粒飼料，並輸出在餵完飼料後，$a_1\sim a_n$ 其中一組可能的解，使得沒有任何一隻魚翻白肚。
Input Format
第一行有一個正整數 $n$，代表魚的數量。
第二行有 $n$ 個正整數 $a_1\sim a_n$，代表每隻魚的大小。
接下來 $n$ 行，第 $i$ 行有兩個正整數 $l_i,r_i$，代表編號 $i$ 的魚的可視範圍。
對於所有測試資料：
- $1\leq n\leq 2\times 10^ 5$
- $1\leq a_i\leq 10^ 9$（$1\leq i\leq n$）
- $1\leq l_i\leq r_i\leq n$（$1\leq i\leq n$）
Output Format
輸出有兩行：
第一行輸出一個整數代表最少要使用幾粒飼料。
第二行輸出 $n$ 個以空白隔開的正整數，代表在使用最少的飼料不讓任何魚翻白肚後，$a_1\sim a_n$ 可以是多少。
若有多組解輸出其中一組即可，注意請滿足題目條件。
Sample Input 1
7 1 2 2
1 3
3 3
2 3
1 4
Sample Output 1
7 2 2 7
Hints
給編號 $2$ 的魚餵 $1$ 粒飼料，給編號 $4$ 的魚餵 $5$ 粒飼料，共使用 $6$ 粒飼料，並且是在滿足條件下使用的最少飼料數。
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資 | 0 |
| 2 | 1~4 | $l_i=1,r_i=i$ | 7 |
| 3 | 1, 5~8 | $n\leq 3000,r_i\leq i$ | 8 |
| 4 | 1~14, 19 | $r_i\leq i$ | 22 |
| 5 | 1, 15~22 | $l_i=r_i$ | 21 |
| 6 | 0~1, 15~26 | $\sum\limits_{i=1}^ n(r_i-l_i+1)\leq 5\times 10^ 5$ | 16 |
| 7 | 0~45 | 無其他限制 | 26 |