#897. SANNEN - San nền

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

Người ta muốn xây dựng một tuyến đường qua một vùng đất. Tuyến đường có chiều dài 𝑛 và được chia thành 𝑛 đoạn. Để làm được việc này thì đầu tiên người ta phải san nền cho vùng đất mà tuyến đường sẽ đi qua.

Ban đầu, nền đường tại đoạn thứ 𝑖 có độ cao là ℎ_𝒊 . Người ta muốn sau khi san nền tại tất cả các đoạn đường để nền đường đều có cùng một độ cao là 𝑘 . Để làm được việc đó thì tại những đoạn mà nền đường có độ cao ℎ_𝒊 > 𝑘 người ta cần đào bỏ đi một lượng đất là ℎ_𝒊 − 𝑘 và tại những đoạn mà nền đường có độ cao ℎ_𝒊 < 𝑘 người ta cần đắp thêm một lượng đất là 𝑘 − ℎ_𝒊 . Tổng lượng đất đào, đắp sẽ là tổng lượng đất phải đào bỏ đi và phải đắp thêm ở 𝑛 đoạn đường.

Yêu cầu: Cho 𝑛 và độ cao của 𝑛 đoạn đường h_1, h2, …, ℎ_𝑛 , với mỗi giá trị của 𝑘 , hãy xác định tổng lượng đất đào, đắp.

Dữ liệu:

  • Dòng đầu tiên ghi hai số nguyên dương 𝑛 𝑚 , trong đó 𝑛 là chiều dài của đoạn đường và 𝑚 là số lượng giá trị 𝑘 cần xác định tổng lượng đất phải đào, đắp ở 𝑛 đoạn đường;
  • Dòng thứ 𝑖 trong 𝑛 dòng tiếp theo ghi số nguyên dương ℎ_𝒊 là độ cao của nền đường tại đoạn thứ 𝑖 ;
  • Dòng thứ 𝑗 trong 𝑚 dòng cuối ghi số nguyên dương 𝑘_𝒋 .

Kết quả:

  • Ghi ra 𝑚 dòng, dòng thứ 𝑗 ghi tổng lượng đất đào, đắp ứng với độ cao 𝑘_𝑗 .

Ví dụ:

Dữ liệu:

4 3
1
3
4
2
1
2
5

Kết quả:

6
4
10

Giới hạn:

  • 1 ≤ 𝑛 ≤ 10^5; 1 ≤ 𝑚 ≤ 10^5; 1 ≤ ℎ_𝒊 ≤ 10^9; 1 ≤ 𝑘_𝒋 ≤ 10^9 ;
  • 50\% số test có 1 ≤ 𝑛 ≤ 2\times 10^4 .