QUEMAX


Submit solution

Points: 100
Time limit: 1.0s
Memory limit: 493M

Problem type

Cho một dãy số \(a_1, a_2, ..., a_n\), ban đầu \(a_i = 0\), với mọi i = 1,2…, n và \(m\) truy vấn dạng \(Q(u, v, k)\) tương ứng tăng các giá trị \(a[u], a[u+1], …, a[v]\) lên một lượng bằng \(k\).

Yêu cầu: Sau \(m\) truy vẫn, hãy tìm giá trị lớn nhất của dãy trên.

Dữ liệu vào:

  • Dòng đầu ghi hai số nguyên dương \(n, m (1 ≤ n ≤ 10^7, 1 ≤ m ≤ 2.10^5)\)

  • \(m\) Dòng tiếp theo, dòng thứ ghi truy vấn gồm ba số nguyên không âm \(u, v, k (1 ≤ u ≤ v ≤ n, 1 ≤ k ≤ 10^9)\)

Dữ liệu ra:

  • Ghi ra một số nguyên duy nhất là giá trị lớn nhất của dãy sau \(m\) truy vấn.

Sample Input

5 3
1 2 100
2 5 100
3 4 100

Sample Output

200

Comments

There are no comments at the moment.