842 . 調查報告

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

aacpschool

User's AC Ratio

83.3% (5/6)

Submission's AC Ratio

42.9% (6/14)

Tags

apcsc apcsc-exam3

Description

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

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

最後調查報告出爐，第 i 位偵探的調查結果顯示，公司 li 到公司 ri 的營業額均不超過 pi 元，其中 p1,p2,…,pm 兩兩相異。

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

Input Format

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

接下來輸入 m 行，第 i 行輸入三個整數 li,ri,pi。

  • 1≤n,m≤105
  • 1≤li≤ri≤n
  • 1≤pi≤109
  • 保證 p1,p2,…,pm 兩兩相異

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≤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