Kenan đã vẽ một sơ đồ các tòa nhà và các đường đi bộ trên cao dọc theo một bên của đại lộ chính ở Baku. Có \(n\) tòa nhà được đánh số từ \(0\) đến \(n-1\) và \(m\) đường đi bộ trên cao được đánh số từ \(0\) đến \(m-1\). Sơ đồ được vẽ trên một mặt phẳng hai chiều, trong đó các tòa nhà là các đoạn thẳng đứng, còn các đường đi bộ trên cao là các đoạn thẳng nằm ngang.

Đáy của tòa nhà \(i\) (\(0 \leq i \leq n-1\)) nằm tại điểm \((x[i], 0)\) và tòa nhà có chiều cao \(h[i]\). Do đó, tòa nhà được biểu diễn bởi đoạn thẳng nối hai điểm \((x[i], 0)\) và \((x[i], h[i])\).

Đường đi bộ trên cao \(j\) (\(0 \leq j \leq m-1\)) có hai đầu mút tại các tòa nhà mang số \(l[j]\) và \(r[j]\), với tung độ dương \(y[j]\). Do đó, đường đi này được biểu diễn bởi đoạn thẳng nối hai điểm \((x[l[j]], y[j])\) và \((x[r[j]], y[j])\).

Một đường đi bộ trên cao và một tòa nhà giao nhau nếu chúng có một điểm chung. Vì vậy, một đường đi bộ trên cao giao với hai tòa nhà tại hai đầu mút của nó, và cũng có thể giao với các tòa nhà khác ở giữa.

Kenan muốn tìm độ dài đường đi ngắn nhất từ đáy tòa nhà \(s\) đến đáy tòa nhà \(g\), với giả thiết rằng một người chỉ có thể đi dọc theo các tòa nhà và các đường đi bộ trên cao, hoặc xác định rằng không tồn tại đường đi như vậy. Lưu ý rằng không được phép đi bộ trên mặt đất, tức là dọc theo đường thẳng nằm ngang có tung độ bằng \(0\).

Một người có thể đi từ một đường đi bộ trên cao vào một tòa nhà hoặc ngược lại tại bất kỳ điểm giao nào. Nếu các đầu mút của hai đường đi bộ trên cao nằm tại cùng một điểm, người đó có thể đi từ đường đi bộ trên cao này sang đường đi bộ trên cao kia.

Nhiệm vụ của bạn là giúp Kenan trả lời câu hỏi trên.

Chi tiết cài đặt

Bạn cần cài đặt hàm sau trong tệp walk.cpp, sử dụng tệp tiêu đề walk.h được cung cấp:

# include "walk.h"

long long min_distance(std::vector<int> x, std::vector<int> h,
                       std::vector<int> l, std::vector<int> r,
                       std::vector<int> y, int s, int g);

• \(x\) và \(h\): các mảng số nguyên có độ dài \(n\), mô tả vị trí và chiều cao của các tòa nhà.
• \(l\), \(r\) và \(y\): các mảng số nguyên có độ dài \(m\), mô tả hai đầu mút và độ cao của các đường đi bộ trên cao.
• \(s\) và \(g\): hai số nguyên chỉ tòa nhà xuất phát và tòa nhà đích.
• Hàm phải trả về độ dài đường đi ngắn nhất giữa đáy tòa nhà \(s\) và đáy tòa nhà \(g\) nếu tồn tại đường đi. Nếu không tồn tại, hàm phải trả về \(-1\).
• Kiểu trả về là số nguyên có dấu 64 bit (long long trong C++, tương ứng với int64 trong mô tả chính thức).
• Trình chấm gọi hàm này đúng một lần cho mỗi trường hợp kiểm thử.

Trình chấm cung cấp hàm main và thực hiện việc đọc, ghi dữ liệu.

Các ví dụ

Ví dụ 1

Xét lời gọi hàm sau, viết theo cú pháp C++:

min_distance({0, 3, 5, 7, 10, 12, 14},
             {8, 7, 9, 7, 6, 6, 9},
             {0, 0, 0, 2, 2, 3, 4},
             {1, 2, 6, 3, 6, 4, 6},
             {1, 6, 8, 1, 7, 2, 5},
             1, 5);

Giá trị trả về đúng là \(27\).

Hình dưới đây minh họa cho Ví dụ 1:

Ví dụ 2

min_distance({0, 4, 5, 6, 9},
             {6, 6, 6, 6, 6},
             {3, 1, 0},
             {4, 3, 2},
             {1, 3, 6},
             0, 4);

Giá trị trả về đúng là \(21\).

Ràng buộc

• \(1 \leq n, m \leq 100\,000\).
• \(0 \leq x[0] < x[1] < \ldots < x[n-1] \leq 10^9\).
• \(1 \leq h[i] \leq 10^9\) với mọi \(0 \leq i \leq n-1\).
• \(0 \leq l[j] < r[j] \leq n-1\) với mọi \(0 \leq j \leq m-1\).
• \(1 \leq y[j] \leq \min(h[l[j]], h[r[j]])\) với mọi \(0 \leq j \leq m-1\).
• \(0 \leq s, g \leq n-1\).
• \(s \neq g\).
• Hai đường đi bộ trên cao không có điểm chung, ngoại trừ có thể tại các đầu mút của chúng.

Giới hạn thời gian: 4 giây. Giới hạn bộ nhớ: 1024 MiB.

Chấm điểm

Tổng điểm là \(100\). Nhóm kiểm thử ví dụ trong gói chính thức có \(0\) điểm.

Trình chấm mẫu

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

Trình chấm mẫu in ra một dòng duy nhất chứa giá trị trả về của min_distance.

Dữ liệu mẫu 1

Đầu vào:

7 7
0 8
3 7
5 9
7 7
10 6
12 6
14 9
0 1 1
0 2 6
0 6 8
2 3 1
2 6 7
3 4 2
4 6 5
1 5

Đầu ra:

27

Dữ liệu mẫu 2

Đầu vào:

5 3
0 6
4 6
5 6
6 6
9 6
3 4 1
1 3 3
0 2 6
0 4

Đầu ra:

21

Nguồn: Đề thi chính thức IOI 2019, ngày thi thứ hai, bài “Sky Walking” (walk); bản tiếng Việt, bản Markdown và gói đính kèm do ban tổ chức cung cấp.