Có một con đường một làn, một chiều từ sân bay Budapest đến khách sạn Forrás. Con đường dài \(L\) kilômét.

Trong sự kiện IOI 2023, \(N+1\) xe buýt đi qua con đường này, được đánh số từ \(0\) đến \(N\). Xe buýt \(i\) (\(0\le i<N\)) dự kiến rời sân bay vào giây thứ \(T[i]\) của sự kiện và có thể đi \(1\) kilômét trong \(W[i]\) giây. Xe buýt \(N\) là xe dự phòng, có thể đi \(1\) kilômét trong \(X\) giây. Thời điểm \(Y\) mà xe dự phòng rời sân bay chưa được xác định.

Thông thường không được phép vượt trên đường, nhưng các xe buýt được vượt nhau tại trạm phân loại. Có \(M\) trạm phân loại (\(M>1\)), đánh số từ \(0\) đến \(M-1\), ở những vị trí khác nhau trên đường. Trạm \(j\) (\(0\le j<M\)) cách sân bay \(S[j]\) kilômét dọc theo đường. Các trạm được sắp xếp theo khoảng cách tăng dần từ sân bay, tức \(S[j]<S[j+1]\) với mỗi \(0\le j\le M-2\). Trạm đầu tiên là sân bay, trạm cuối là khách sạn: \(S[0]=0\) và \(S[M-1]=L\).

Mỗi xe buýt đi với tốc độ tối đa, trừ khi đuổi kịp một xe chậm hơn phía trước. Khi đó, chúng bị dồn lại và phải đi với tốc độ của xe chậm hơn cho đến trạm phân loại tiếp theo. Tại đó, các xe nhanh hơn sẽ vượt các xe chậm hơn.

Cụ thể, với mỗi \(0\le i\le N\) và \(0\le j<M\), thời điểm \(t_{i,j}\) (tính bằng giây) mà xe buýt \(i\) đến trạm \(j\) được xác định như sau. Đặt \(t_{i,0}=T[i]\) với mỗi \(0\le i<N\), và \(t_{N,0}=Y\). Với mỗi \(j\) thỏa mãn \(0<j<M\):

• Thời điểm dự kiến đến trạm \(j\) của xe \(i\), ký hiệu \(e_{i,j}\), là thời điểm xe đến trạm \(j\) nếu đi với tốc độ tối đa kể từ khi đến trạm \(j-1\). Tức là:

• Xe \(i\) đến trạm \(j\) tại thời điểm lớn nhất trong các thời điểm dự kiến đến của chính nó và của mọi xe khác đã đến trạm \(j-1\) sớm hơn nó. Cụ thể, \(t_{i,j}\) là giá trị lớn nhất của \(e_{i,j}\) và mọi \(e_{k,j}\) thỏa mãn \(0\le k\le N\) và \(t_{k,j-1}<t_{i,j-1}\).

Ban tổ chức IOI muốn lên lịch cho xe dự phòng (xe \(N\)). Nhiệm vụ của bạn là trả lời \(Q\) câu hỏi: cho thời điểm \(Y\) (tính bằng giây) xe dự phòng rời sân bay, xe sẽ đến khách sạn vào thời điểm nào?

Chi tiết cài đặt

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

void init(int L, int N, std::vector<long long> T, std::vector<int> W,
          int X, int M, std::vector<int> S);

• \(L\): chiều dài con đường.
• \(N\): số xe buýt không phải xe dự phòng.
• \(T\): mảng độ dài \(N\) mô tả thời điểm khởi hành dự kiến từ sân bay của các xe không phải xe dự phòng.
• \(W\): mảng độ dài \(N\) mô tả tốc độ tối đa của các xe không phải xe dự phòng.
• \(X\): thời gian để xe dự phòng đi \(1\) kilômét.
• \(M\): số trạm phân loại.
• \(S\): mảng độ dài \(M\) mô tả khoảng cách từ sân bay đến các trạm phân loại.
• Hàm được gọi đúng một lần cho mỗi test, trước mọi lời gọi arrival_time.

long long arrival_time(long long Y);

• \(Y\): thời điểm xe dự phòng (xe \(N\)) dự kiến rời sân bay.
• Hàm cần trả về thời điểm xe dự phòng đến khách sạn.
• Hàm được gọi đúng \(Q\) lần.

Ví dụ

Xét dãy lời gọi sau:

init(6, 4, [20, 10, 40, 0], [5, 20, 20, 30], 10, 4, [0, 1, 3, 6])

Bỏ qua xe \(4\) chưa được lên lịch, bảng sau cho biết thời điểm đến dự kiến và thực tế của các xe không phải xe dự phòng tại mỗi trạm:

Thời điểm đến trạm \(0\) là thời điểm dự kiến rời sân bay: \(t_{i,0}=T[i]\) với \(0\le i\le 3\).

Các thời điểm dự kiến đến trạm \(1\) được tính như sau:

• Xe \(0\): \(e_{0,1}=t_{0,0}+W[0]\cdot(S[1]-S[0])=20+5\cdot1=25\).
• Xe \(1\): \(e_{1,1}=t_{1,0}+W[1]\cdot(S[1]-S[0])=10+20\cdot1=30\).
• Xe \(2\): \(e_{2,1}=t_{2,0}+W[2]\cdot(S[1]-S[0])=40+20\cdot1=60\).
• Xe \(3\): \(e_{3,1}=t_{3,0}+W[3]\cdot(S[1]-S[0])=0+30\cdot1=30\).

Các thời điểm thực tế đến trạm \(1\) được tính như sau:

• Xe \(1\) và \(3\) đến trạm \(0\) sớm hơn xe \(0\), nên \(t_{0,1}=\max([e_{0,1},e_{1,1},e_{3,1}])=30\).
• Xe \(3\) đến trạm \(0\) sớm hơn xe \(1\), nên \(t_{1,1}=\max([e_{1,1},e_{3,1}])=30\).
• Xe \(0\), \(1\) và \(3\) đến trạm \(0\) sớm hơn xe \(2\), nên \(t_{2,1}=\max([e_{0,1},e_{1,1},e_{2,1},e_{3,1}])=60\).
• Không xe nào đến trạm \(0\) sớm hơn xe \(3\), nên \(t_{3,1}=\max([e_{3,1}])=30\).

arrival_time(0)

Xe \(4\) mất \(10\) giây để đi \(1\) kilômét và được lên lịch rời sân bay ở giây thứ \(0\). Bảng sau cho biết các thời điểm đến của mỗi xe. Thay đổi duy nhất trong thời điểm đến dự kiến và thực tế của các xe không phải xe dự phòng được gạch chân.

Xe \(4\) đến khách sạn ở giây thứ \(60\). Vì vậy, hàm cần trả về \(60\).

arrival_time(50)

Xe \(4\) được lên lịch rời sân bay ở giây thứ \(50\). Các thời điểm đến của các xe không phải xe dự phòng không thay đổi so với bảng ban đầu. Các thời điểm đến được thể hiện trong bảng sau:

Xe \(4\) vượt xe \(2\) chậm hơn tại trạm \(1\) khi chúng đến cùng lúc. Tiếp theo, xe \(4\) bị dồn lại với xe \(3\) giữa trạm \(1\) và trạm \(2\), khiến xe \(4\) đến trạm \(2\) ở giây thứ \(90\) thay vì \(80\). Sau khi rời trạm \(2\), xe \(4\) bị dồn lại với xe \(1\) cho đến khách sạn. Xe \(4\) đến khách sạn ở giây thứ \(130\), nên hàm cần trả về \(130\).

Ta có thể vẽ đồ thị thời điểm mỗi xe đến từng khoảng cách từ sân bay. Trục \(x\) biểu diễn khoảng cách từ sân bay (kilômét), trục \(y\) biểu diễn thời điểm (giây). Các đường nét đứt dọc đánh dấu vị trí trạm phân loại. Các đường liền nét khác nhau, kèm chỉ số xe, biểu diễn bốn xe không phải xe dự phòng. Đường chấm màu đen biểu diễn xe dự phòng.

Đồ thị cho arrival_time(0):

Đồ thị cho arrival_time(50):

Các ràng buộc

• \(1\le L\le 10^9\).
• \(1\le N\le 1\,000\).
• \(0\le T[i]\le 10^{18}\) với mỗi \(0\le i<N\).
• \(1\le W[i]\le 10^9\) với mỗi \(0\le i<N\).
• \(1\le X\le 10^9\).
• \(2\le M\le 1\,000\).
• \(0=S[0]<S[1]<\cdots<S[M-1]=L\).
• \(1\le Q\le 10^6\).
• \(0\le Y\le 10^{18}\).

Các subtask

Trình chấm mẫu

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

dòng 1: L N X M Q
dòng 2: T[0] T[1] … T[N − 1]
dòng 3: W[0] W[1] … W[N − 1]
dòng 4: S[0] S[1] … S[M − 1]
dòng 5 + k (0 ≤ k < Q): Y cho câu hỏi k

Trình chấm mẫu in các câu trả lời theo định dạng sau:

dòng 1 + k (0 ≤ k < Q): giá trị trả về của arrival_time cho câu hỏi k

Nguồn: Olympic Tin học Quốc tế 2023 (IOI 2023). Bản dịch tiếng Việt chính thức của đoàn Việt Nam, được đối chiếu với đề tiếng Anh chính thức. Nội dung đề được phát hành theo giấy phép CC BY.