Bài tập

Thành phố \(S\) có \(N\) thị trấn nhỏ, thị trấn \(i\) có \(C[i]\) người dân sinh sống và giữa 2 thành phố có tối đa một con đường một chiều đi từ thành phố này đến thành phố kia.
Hiện nay thành phố đang chịu ảnh hưởng nghiêm trọng của dịch bệnh, mỗi người dân bị hạn chế đi ra ngoài, bởi vậy nên chính quyền thành phố phải cử bộ đội đi cung cấp nhu yếu phẩm cho mọi người. Giả sử các anh bộ đội xuất phát tại thị trấn \(i\), họ sẽ thông qua những con đường một chiều để đi đến những thị trấn khác, thăm và phát nhu yếu phẩm cho tất cả người dân sinh sống trên thị trấn họ đi qua (lưu ý: mỗi người dân chỉ được thăm và phát nhu yếu phẩm 1 lần).

Yêu cầu đặt ra là với mỗi thị trấn xuất phát, thì có thể thăm và phát nhu yếu phẩm cho tối đa bao nhiêu người dân?

Input

• Dòng đầu tiên gồm 2 số \(N\) và \(M\), tương ứng số thị trấn trong thành phố \(S\), và số con đường một chiều

• Dòng tiếp theo gồm \(N\) số nguyên tương ứng số dân sinh sống tại từng thị trấn

• \(M\) dòng tiếp theo, mỗi dòng gồm 2 số \(u\) và \(v\), tương ứng có con đường từ thị trấn \(u\) đến thị trấn \(v\)

Output

• Gồm một dòng duy nhất ghi \(N\) số nguyên, số thứ \(u\) tương ứng với số người dân tối đa có thể được thăm và phát nhu yếu phẩm nếu như xuất phát tại thị trấn \(u\). Các số cách nhau bởi 1 khoảng trắng.

Example

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

22 21 21 21 21 6 7 

Scoring

• \(30\%\) số tests có \(1 \le N, M \le 1000\)

• \(70\%\) số tests có \(1 \le N, M \le 100000\)

Cô giáo trường tiểu học \(X\) đang dạy \(n\) học sinh tập xe đạp, các học sinh được đánh số từ \(1\) tới \(n\), học sinh thứ \(j\) có trọng lượng là \(a_{j}\). Có một xe đạp duy nhất với tải trọng là \(m\), hai học sinh chỉ có thể cùng lên xe nếu tổng trọng lượng của hai học sinh không vượt quá \(m\).

Cô giáo tự hỏi có bao nhiêu cách chọn hai học sinh khác nhau cho cùng lên xe, sau nhiều giờ tính toán không có kết quả, cô quyết định hỏi các chuyên gia lập trình giải bài toán Counting Student Pairs (CSP)

Yêu cầu: Đếm số cặp chỉ số \(i, j\) trong đó \(i < j\) và \(a_i + a_j \leq m\)

Input

• Dòng \(1\) chứa hai số nguyên dương \(n, m\ (m \leq 10^6)\)
• Dòng \(2\) chứa \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) (\(\forall{i}: a_i \leq 10^6\))

Output

Ghi một số nguyên duy nhất là đáp số

Example

10 18
8 4 14 3 17 9 4 14 8 3

29

Scoring

• Subtask \(1\) (\(60\%\) số điểm): \(n \leq 10^4\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \leq 10^5\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \leq 10^6\).

Tương truyền, San Hà Xã Tắc Đồ là một pháp bảo vô cùng cường đại do Nữ Oa nương nương thời thượng
cổ lưu lại. Uy lực của bức họa này có thể tạo dựng cả một thế giới riêng -- thiên địa sinh thành, nhật nguyệt vận hành, vạn vật hữu linh đều có thể hiện ra trong tranh. Ai nắm giữ được bức họa, chẳng khác nào nắm giữ một cõi thế giới riêng biệt trong lòng bàn tay.

Lâm là một đạo sĩ đã tu luyện đến cảnh giới gần kề thánh nhân, trong một lần cơ duyên gặp gỡ, tìm được một bức họa cổ, tương truyền là bản phác San Hà Xã Tắc Đồ.

Sau nhiều năm tu hành và nghiên ngẫm, ông Lâm quyết định dựng lại bức họa, từng đoạn từng nét. Bức tranh cần được vẽ lên một tấm lụa dài \(n\) thước, chia làm \(n\) đoạn liên tiếp, mỗi đoạn ứng với một phần của thế giới trong tranh. Ông đã xác định được mức màu sắc thích hợp cho từng đoạn, được lưu dưới dạng dãy chuỗi dài \(n\) số, mỗi số cho biết độ sáng, tối tương ứng được sử dụng.

Ban đầu, toàn bộ tấm lụa trắng trơn. Mỗi lần hành pháp (tức là vẽ), ông có thể tô một đoạn liên tiếp trên lụa bằng một màu duy nhất, nhưng ông không được tô màu sáng hơn lên màu tối hơn, vì điều đó sẽ khiến thiên địa trong tranh lộn ngược, âm dương đảo lộn. Chỉ có thể tô màu tối hơn chỗ chưa vẽ, hoặc lên màu sáng hơn.

Tuy nhiên, do thiên mệnh hữu hạn, Lâm không thể hoàn thành toàn bộ bức họa trong một lần. Vì thế, ông đang cân nhắc bỏ trống một số đoạn nhất định, không vẽ vào đó nữa -- để sau này hậu nhân hoàn thiện. Hiện tại có \(q\) kịch bản khác nhau, mỗi kịch bản cho biết một đoạn liên tiếp từ \(l\) đến \(r\) trên tấm lụa sẽ được vẽ.

Yêu cầu: Với mỗi kịch bản như vậy, hãy giúp ông Lâm tính xem: số lần hành pháp (vẽ) ít nhất cần thiết để hoàn thành bức họa, đúng theo màu sắc đã định, và không vi phạm quy tắc sáng tối.

Input

• Dòng đầu tiên gồm hai số nguyên \(n, q\) (\(n, q \leq 10^5\)) là số đoạn của tấm lụa và số kịch bản.
• Dòng thứ hai là \(n\) số \(a_1, a_2, \dots, a_n\) (\(0 \leq a_i \leq 10^9\)) biểu thị độ sáng tối của từng đoạn.
• \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l\) và \(r\) (\(1 \leq l \leq r \leq n\)) cho biết đoạn sẽ vẽ.

Output

• Với mỗi kịch bản, in ra một dòng chứa số nguyên là số lần vẽ tối thiểu cần thiết để hoàn thành bức họa.

Example

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

2
4
4
3
5

Scoring

• \(30\%\) số điểm thỏa mãn \(n, q \leq 100\)
• \(20\%\) số điểm khác với \(n, q \leq 1000\)
• Còn lại không có điều kiện gì thêm

Trường Đại học Công nghệ Tương lai vừa cho ra mắt một hệ thống AI đặc biệt mang tên "Mai Mối Chuẩn Gen", với nhiệm vụ giúp sinh viên cô đơn tìm được nửa kia phù hợp nhất dựa trên chỉ số "tương thích cảm xúc".

Có \(n\) sinh viên tham gia hệ thống, mỗi người được hệ thống đánh giá bằng một chỉ số \(a_1, a_2, ..., a_n\) thể hiện mức độ đồng điệu về cảm xúc.

Hệ thống hoạt động bằng cách chia dãy chỉ số cảm xúc thành các đoạn con liên tiếp, không giao nhau. Một đoạn được xem là tối ưu nếu trung bình cộng của các chỉ số trong đoạn đúng bằng một giá trị lý tưởng \(x\) mà hệ thống đưa ra.

Mỗi khi có sinh viên đăng ký tham gia, hệ thống sẽ yêu cầu trả lời một truy vấn dạng:

Trong khoảng từ người thứ \(l\) đến người thứ \(r\), có thể chia được tối đa bao nhiêu đoạn con liên tiếp, không giao nhau sao cho trung bình cộng của mỗi đoạn đúng bằng \(x\)?

Bạn được giao nhiệm vụ xử lý \(q\) truy vấn như vậy, để giúp hệ thống hoạt động hiệu quả hơn!

Input

• Dòng đầu tiên chứa ba số nguyên \(n\), \(q\), \(x\) \((1 \le n, q \le 2 \cdot 10^5, 1 \le x \le 10^6)\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, ..., a_n\) là chỉ số cảm xúc của từng sinh viên \((1 \le a_i \le 10^6)\).
• \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l_i\), \(r_i\) \((1 \le l_i \le r_i \le n)\).

Output

• Gồm \(q\) dòng, dòng thứ \(i\) là đáp án cho truy vấn thứ \(i\) --- số đoạn con liên tiếp, không giao nhau trong đoạn \([l_i, r_i]\) sao cho trung bình cộng đúng bằng \(x\).

Example

10 1 5
6 7 2 5 6 1 8 7 4 6
1 10

4

Scoring

• Có \(30\%\) số test tương ứng với \(30\%\) số điểm có \(n, q \leq 200\).
• Có \(30\%\) số test tương ứng với \(30\%\) số điểm có \(n, q \leq 2000\).
• Có \(40\%\) số test tương ứng với \(40\%\) số điểm không có ràng buộc gì thêm.