Bài 4. Trồng cây (HSG THPT Thành phố Huế 2026)

Xem dạng PDF

Gửi bài giải

Điểm: 1,00 (OI)
Giới hạn thời gian: 2.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Tác giả:
Nguồn bài:
HSG THPT Thành phố Huế 2026
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Để tạo bóng mát, thành phố ~X~ muốn trồng cây xanh dọc các tuyến đường. Trước khi tiến hành trồng đại trà, đội nghiên cứu đã xây dựng một mô hình thử nghiệm. Ban đầu có ~N~ cây, các cây được đánh số từ 1 đến ~N~, cây thứ ~i~ có chiều cao ~H_i~. Có tất cả ~Q~ phương án chăm sóc được đề xuất, phương án thứ ~i~ có dạng ~(L_i, R_i, D_i)~ có nghĩa là thực hiện chăm sóc các cây từ ~L_i~ đến ~R_i~ cao thêm ~D_i~. Sau đó, đội nghiên cứu đã lập một bản kế hoạch ~M~ ngày, kế hoạch cho ngày thứ ~j~ có dạng ~(U_j, V_j, C_j)~ có nghĩa là thực hiện các phương án từ ~U_j~ đến ~V_j~, mỗi phương án ~C_j~ lần.

Tính chiều cao cuối cùng của ~N~ cây sau khi thực hiện xong toàn bộ kế hoạch. Vì kết quả có thể rất lớn nên hãy in ra phần dư của kết quả khi chia cho ~10^9 + 7~.

Dữ liệu vào

Gồm các dòng:

  • Dòng 1: Chứa ba số nguyên dương ~N, Q, M (1 \le N, Q, M \le 2 \times 10^6)~.
  • Dòng 2: Chứa ~N~ số nguyên không âm ~H_1, H_2, \ldots, H_N (0 \le H_i \le 10^9)~.
  • ~Q~ dòng tiếp theo chứa các phương án chăm sóc có dạng ~L_i, R_i, D_i (1 \le i \le Q, 1 \le L_i \le R_i \le N, 0 \le D_i \le 10^9)~.
  • ~M~ dòng tiếp theo thể hiện bản kế hoạch của đội, mỗi dòng có dạng ~U_j, V_j, C_j (0 \le C_j \le 10^9)~.

Kết quả

~N~ số nguyên trên một dòng, tương ứng chiều cao của hàng cây sau khi thực hiện xong toàn bộ kế hoạch. Kết quả in ra phần dư khi chia cho ~10^9 + 7~.

Ví dụ

Input 1

5 3 2
10 0 5 0 7
2 4 3
1 3 2
3 5 1
1 2 2
2 3 1

Output 1

16 12 18 7 8

Ngày thứ nhất thực hiện phương án 1 và 2, mỗi phương án hai lần: chiều cao lần lượt thành 10 6 11 6 7 rồi 14 10 15 6 7. Ngày thứ hai thực hiện phương án 2 và 3, mỗi phương án một lần: 16 12 17 6 7 rồi 16 12 18 7 8. Lưu ý: bảng dữ liệu ra hiển thị trên trang đề bị mất một chữ số ở giá trị thứ hai; chuỗi kết quả đúng theo chính phần giải thích của đề (và theo cả bản vét cạn lẫn bản tối ưu trong tài liệu này) là 16 12 18 7 8.

Ràng buộc

  • Có 40% số điểm tương ứng với ~1 \le N, Q, M \le 500~.

Chương trình đọc dữ liệu từ bàn phím (stdin) và ghi kết quả ra màn hình (stdout).


Đang tải...