Elearning CodePath – CTP Online Judge

Máy chủ ưu tiên

stockpq

🟢 Easy #Priority Queue

Có N công việc cần xử lý trên một máy chủ. Công việc i xuất hiện tại thời điểm ti, cần di đơn vị thời gian để hoàn thành và có mức ưu tiên pi.

Tại mỗi thời điểm máy chủ rảnh, trong các công việc đã xuất hiện nhưng chưa làm, máy chủ chọn công việc có pi lớn nhất. Nếu hòa, chọn công việc có di nhỏ hơn; nếu vẫn hòa, chọn chỉ số nhỏ hơn.

Gọi C_i là thời điểm hoàn thành công việc i. Hãy tính tổng pi · C_i theo modulo 1 000 000 007.

**Yêu cầu:** Viết chương trình giải bài toán trên.

**Dữ liệu vào:** Vào từ file `stockpq.INP` gồm:

- Dòng 1 chứa N.
- N dòng tiếp theo, dòng i chứa ti, di, pi.

**Kết quả:** Ghi ra file `stockpq.OUT` gồm:

- Một số nguyên duy nhất là tổng cần tìm modulo 1 000 000 007.

**Ràng buộc:**

- 1 ≤ N ≤ 2·10^5
- 0 ≤ ti ≤ 10^9
- 1 ≤ di, pi ≤ 10^9

**Ví dụ 1**

| Input | Output | Giải thích |
|---|---|---|
| 4<br>0 3 5<br>1 2 9<br>4 1 4<br>6 2 8 | 148 | Thứ tự xử lý là 1,2,3,4; thời điểm hoàn thành lần lượt 3,5,6,8. Tổng là 5·3 + 9·5 + 4·6 + 8·8 = 148. |

**Phân chia subtask:**

- Subtask 1 (30% số điểm): N ≤ 2000.
- Subtask 2 (30% số điểm): Các ti đã được nhập theo thứ tự không giảm.
- Subtask 3 (40% số điểm): Không có ràng buộc gì thêm.

✅ Đã AC: 0 / 0 submissions