842 . 調查報告

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

wilson

User's AC Ratio

80.0% (4/5)

Submission's AC Ratio

45.5% (5/11)

Tags

apcsc apcsc-exam3

Description

APCSC 公司長期在跟 $n$ 間敵對公司對抗，這些公司編號為 $1,2,\ldots,n$。

APCSC 公司的老闆想調查這些敵對公司的營業額，為此，他們派了 $m$ 個偵探去秘密調查，為了不被發現，偵探只能調查一部分的敵對公司，而且也只能問到這幾間公司營業額最大值的上限。

最後調查報告出爐，第 $i$ 位偵探的調查結果顯示，公司 $l_i$ 到公司 $r_i$ 的營業額均不超過 $p_i$ 元，其中 $p_1,p_2,\ldots,p_m$ 兩兩相異。

有了這些資訊，APCSC 公司的老闆想知道這 $n$ 間敵對公司的營業額總和最大是多少？可是這位老闆不太會寫程式，所以他委託你幫他算出來。

Input Format

第一行輸入兩個正整數 $n,m$。

接下來輸入 $m$ 行，第 $i$ 行輸入三個整數 $l_i,r_i,p_i$。

  • $1\le n,m\le 10^ 5$
  • $1\le l_i\le r_i\le n$
  • $1\le p_i\le 10^ 9$
  • 保證 $p_1,p_2,\ldots,p_m$ 兩兩相異

Output Format

如果營業額總和沒有上限，則輸出 infinity，否則輸出一個整數，代表營業額總和的最大值。

Sample Input 1

6 4
1 2 3
4 5 2
2 6 4
3 3 8

Sample Output 1

18

Sample Input 2

10 5
1 2 4
3 4 5
6 7 3
7 9 1
9 10 100

Sample Output 2

infinity

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~10 $n,m\le 1000$ 40
3 0~16 無額外限制 60

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2 3
1 1000 524288 65536 1 2 3
2 1000 524288 65536 2 3
3 1000 524288 65536 2 3
4 1000 524288 65536 2 3
5 1000 524288 65536 2 3
6 1000 524288 65536 2 3
7 1000 524288 65536 2 3
8 1000 524288 65536 2 3
9 1000 524288 65536 2 3
10 1000 524288 65536 2 3
11 1000 524288 65536 3
12 1000 524288 65536 3
13 1000 524288 65536 3
14 1000 524288 65536 3
15 1000 524288 65536 3
16 1000 524288 65536 3
Submit
Back to Top