Đề bài

Trong một vũ trụ khác, Vlad bị mắc kẹt trong một phiên bản tương lai của pháo đài Poenari gồm \(n\) tầng, được đánh số từ \(0\) đến \(n-1\). Từ mỗi tầng \(i\), Vlad chỉ có thể đi lên theo một trong hai cách:

• Đi cầu thang, tốn \(1\) giọt máu. Cầu thang từ tầng \(i\) cho phép Vlad đi lên nhiều nhất \(v[i]\) tầng, tức là đến bất kỳ tầng nào từ \(i+1\) đến \(i+v[i]\) mà không vượt quá tầng \(n-1\).
• Hóa thành dơi và đi qua ống thông gió, tốn \(2\) giọt máu. Ống thông gió từ tầng \(i\) cho phép Vlad đi lên nhiều nhất \(w[i]\) tầng, tức là đến bất kỳ tầng nào từ \(i+1\) đến \(i+w[i]\) mà không vượt quá tầng \(n-1\).

Hai người anh em của Vlad là Radu và Mircea đưa ra \(m\) kịch bản. Mỗi kịch bản gồm hai tầng \(A\) và \(B\) với \(A\le B\). Với mỗi kịch bản, hãy tìm số giọt máu ít nhất Vlad phải trả để đi từ tầng \(A\) đến tầng \(B\).

Chi tiết cài đặt

Bạn cần cài đặt hàm sau:

std::vector<int> solve(
    std::vector<int>& v,
    std::vector<int>& w,
    std::vector<std::pair<int, int>>& queries
);

• v: mảng độ dài \(n\); v[i] là số tầng nhiều nhất cầu thang tại tầng \(i\) có thể đưa Vlad đi lên.
• w: mảng độ dài \(n\); w[i] là số tầng nhiều nhất hệ thống ống thông gió tại tầng \(i\) có thể đưa Vlad đi lên.
• queries: mảng độ dài \(m\) gồm các cặp \((A,B)\) như mô tả trong đề.
• Hàm phải trả về một mảng độ dài \(m\), trong đó phần tử thứ \(i\) là đáp án của truy vấn thứ \(i\).

Ràng buộc

• \(1\le n,m\le500\,000\).
• \(1\le v[i],w[i]\le n\) với mọi \(0\le i<n\).
• \(0\le A\le B\le n-1\) với mọi truy vấn.

Phân nhóm

• Phân nhóm 1 (5 điểm): \(1\le n\le300\), \(1\le m\le500\,000\).
• Phân nhóm 2 (7 điểm): \(1\le n\le3\,000\), \(1\le m\le3\,000\).
• Phân nhóm 3 (11 điểm): \(1\le n\le20\,000\), \(1\le m\le20\,000\).
• Phân nhóm 4 (44 điểm): \(1\le n\le200\,000\), \(1\le m\le200\,000\).
• Phân nhóm 5 (8 điểm): \(1\le n,m\le500\,000\); với mọi \(0\le i<j\le n-1\), ta có \(v[i]\le v[j]\) và \(w[i]\le w[j]\).
• Phân nhóm 6 (25 điểm): Không có ràng buộc bổ sung.

Ví dụ

solve(
    {2, 3, 1, 1, 1, 1, 2},
    {3, 4, 1, 2, 1, 2, 2},
    {{0, 4}, {0, 5}, {0, 6}}
)

{2, 3, 4}

solve(
    {1, 1, 1, 2, 3, 2, 1, 1, 2, 3},
    {2, 4, 1, 4, 1, 4, 1, 3, 2, 3},
    {{3, 9}, {0, 9}, {0, 7}, {0, 4}, {3, 5}}
)

{3, 5, 4, 3, 1}

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu theo định dạng sau:

• Dòng \(1\): \(n\).
• Dòng \(2\): v[0] v[1] ... v[n-1].
• Dòng \(3\): w[0] w[1] ... w[n-1].
• Dòng \(4\): \(m\).
• Dòng \(5+i\) với \(0\le i<m\): A B của truy vấn thứ \(i\).

Trình chấm mẫu in \(m\) dòng là các phần tử của mảng do solve trả về.