Cuộn Cỏ Khô

Điểm: 1,00 (OI)

Giới hạn thời gian: 4.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Farmer John quản lý một cây nhị phân có $N$ nút (lẻ). Nút $i$ có cha là $⌊ i / 2 ⌋$ . Mỗi nút $i$ có giá trị ban đầu $a_{i}$ và chi phí thay đổi $c_{i}$ .

Thuật toán xấp xỉ trung vị hoạt động từ nút $N$ đến nút $1$ : tại mỗi bước, nếu giá trị nút hiện tại không phải trung vị của nó và hai con, FJ hoán đổi giá trị nút hiện tại với con có giá trị là trung vị. Giá trị cuối cùng tại nút 1 là kết quả xấp xỉ.

FJ có thể thay đổi giá trị của nút $i$ thành bất kỳ giá trị nào với chi phí $c_{i}$ (hoặc giữ nguyên miễn phí). Cho $Q$ truy vấn, mỗi truy vấn cho giá trị mục tiêu $m$ , hãy tìm chi phí tối thiểu để thuật toán trả về $m$ .

Dữ liệu vào

Dòng 1: Số nguyên $N$
$N$ dòng tiếp: Hai số $a_{i}$ và $c_{i}$
Dòng tiếp: Số nguyên $Q$
$Q$ dòng tiếp: Mỗi dòng một số $m$

Dữ liệu ra

$Q$ dòng, mỗi dòng chứa chi phí tối thiểu cho truy vấn tương ứng.

Ràng buộc

$N, Q \leq 2 \cdot 10^{5}$ , $N$ lẻ
$0 \leq a_{i}, c_{i}, m \leq 10^{9}$
Giới hạn thời gian: 4 giây

Ví dụ

Input	Output	Giải thích
5 10 10000 30 1000 20 100 50 10 40 1 11 55 50 45 40 35 30 25 20 15 10 5	111 101 101 100 100 100 100 0 11 11 111	Với $m = 20$ : không cần thay đổi gì (chi phí 0) vì thuật toán đã trả về 20.

Bình luận

Không có bình luận tại thời điểm này.