Mỗi buổi sáng, tàu tốc hành chạy ngang qua trang trại để tới thành phố lớn; mỗi buổi chiều, nó chạy ngang qua theo hướng ngược lại để trở về vùng ngoại ô. Hôm nay, Bessie dành thời gian quan sát đoàn tàu cả buổi sáng lẫn buổi chiều.

Bessie biết trước rằng đoàn tàu có \(N\) toa (\(1 \leq N \leq 10^6\)), được đánh số thuận tiện từ \(0 \dots N-1\). Toa \(i\) có ghi số ID \(c_i\) (\(0 \leq c_i \leq 10^9\)). Tất cả các số đều nhìn thấy được cả vào buổi sáng lẫn buổi chiều, nên Bessie có hai cơ hội quan sát số của mỗi toa. Cụ thể, khi đoàn tàu chạy ngang qua vào buổi sáng, Bessie quan sát được \(c_0\), tiếp theo là \(c_1\), và cứ thế cho đến \(c_{N-1}\). Khi đoàn tàu chạy ngang qua vào buổi chiều, cô lại quan sát được \(c_0\), tiếp theo là \(c_1\), và cứ thế cho đến \(c_{N-1}\).

Bessie đã chọn một số nguyên \(K\) (\(1 \leq K \leq N\)), và cô muốn xác định số ID nhỏ nhất trong mỗi đoạn gồm \(K\) toa liên tiếp. Cô có một cuốn sổ để thực hiện tính toán, nhưng nó khá nhỏ, còn chữ viết tay (hay viết móng?) của cô lại khá lớn. Chẳng hạn, sổ thậm chí có thể không đủ chỗ để ghi cả \(N+1-K\) giá trị nhỏ nhất. Vì những lý do khó hiểu, Bessie sẵn lòng kêu các giá trị nhỏ nhất lên trời ngay khi tính được, nên ít nhất điều này không phải là vấn đề.

Đoàn tàu sắp tới! Hãy giúp Bessie tìm \(N+1-K\) giá trị nhỏ nhất khi đoàn tàu chạy ngang qua hai lần, đồng thời bảo đảm cô sử dụng hiệu quả cuốn sổ có dung lượng hạn chế. Cuốn sổ được chia thành \(5500\) ô, được đánh số thuận tiện từ \(0 \dots 5499\), và mỗi ô có thể lưu chính xác một số nguyên trong đoạn từ \(-2^{31}\) đến \(2^{31}-1\), kể cả hai đầu mút. Ban đầu, mỗi ô lưu số nguyên \(0\).

Giao thức tương tác

Đây là một bài tương tác, nhưng bạn sẽ không sử dụng I/O chuẩn hoặc I/O tệp. Cụ thể, bạn phải cài đặt hàm sau để giúp Bessie quản lý hiệu quả không gian hạn chế trong cuốn sổ:

void helpBessie(int ID);

Mỗi khi một toa tàu chạy ngang qua, cả vào buổi sáng lẫn buổi chiều, hàm của bạn sẽ được gọi và đầu vào của hàm là số ID ghi trên toa tàu đó.

Trong phần cài đặt hàm helpBessie, bạn có thể gọi các hàm sau:

• int get(int index): lấy giá trị số nguyên được lưu tại chỉ số đã cho trong sổ của Bessie.
• void set(int index, int value): đặt số nguyên tại chỉ số đã cho thành giá trị đã cho.
• void shoutMinimum(int output): yêu cầu Bessie kêu số đã cho lên trời.
• int getTrainLength(): trả về \(N\), số toa tàu.
• int getWindowLength(): trả về \(K\), độ dài cửa sổ.
• int getCurrentCarIndex(): trả về chỉ số của toa tàu hiện đang chạy ngang qua.
• int getCurrentPassIndex(): trả về \(0\) nếu Bessie đang quan sát lượt tàu buổi sáng và trả về \(1\) nếu cô đang quan sát lượt tàu buổi chiều.

Để giúp bạn bắt đầu viết mã, đề bài cung cấp các mã mẫu ban đầu cho C/C++ và Java. Rất tiếc, bài này không hỗ trợ bài nộp bằng Python hoặc Pascal.

Các giá trị nhỏ nhất của cửa sổ phải được xuất theo đúng thứ tự: giá trị nhỏ nhất trên các toa \(0, 1, \dots, K-1\) phải được xuất trước giá trị nhỏ nhất trên các toa \(1, 2, \dots, K\), và cứ tiếp tục như vậy. Ngoài ràng buộc về thứ tự này, hàm của bạn có thể xuất các giá trị nhỏ nhất trong bất kỳ lần gọi hàm nào và vào bất kỳ thời điểm nào. Chẳng hạn, hàm có thể không tạo ra đầu ra trong một số lần gọi và tạo ra nhiều đầu ra trong những lần gọi khác.

Bessie có trí nhớ ngắn hạn tuyệt vời, vì vậy không có hạn chế nào về bộ nhớ được sử dụng bên trong hàm helpBessie, ngoài giới hạn thông thường là 256 MB. Tuy nhiên, giữa hai toa tàu, Bessie không thể “nhớ” bất cứ điều gì không được lưu trong sổ. Vì vậy, giữa các lần gọi hàm, chương trình không được duy trì trạng thái nào ngoài trạng thái được lưu thông qua các lời gọi get và set.

Điều này có nghĩa là:

Bạn KHÔNG ĐƯỢC PHÉP tạo bất kỳ biến toàn cục hoặc biến tĩnh không phải hằng số nào. Mọi lời giải làm như vậy sẽ bị loại. Các huấn luyện viên SẼ kiểm tra thủ công để xác minh lời giải tuân thủ tinh thần của bài toán. Vì bài này không cần I/O tệp, bạn cũng KHÔNG ĐƯỢC PHÉP thực hiện bất kỳ thao tác I/O tệp nào trong mã.

Tổng số lời gọi set cộng với tổng số lời gọi get mà chương trình thực hiện được giới hạn ở \(25 \cdot 10^6\) cho mỗi bộ dữ liệu kiểm tra.

Dữ liệu vào

Bạn không đọc dữ liệu trực tiếp từ đầu vào chuẩn. Bộ chấm biết trước \(N\), \(K\) và dãy \(c_0, c_1, \dots, c_{N-1}\); trong mỗi lượt tàu chạy qua, bộ chấm lần lượt gọi helpBessie(c_i) với \(i=0,1,\dots,N-1\). Định dạng hiển thị trong ví dụ gồm \(N\), \(K\) trên dòng đầu và \(N\) số ID trên dòng thứ hai.

Dữ liệu ra

Bạn không ghi trực tiếp ra đầu ra chuẩn. Hãy gọi shoutMinimum đúng \(N+1-K\) lần để báo các giá trị nhỏ nhất của các cửa sổ theo thứ tự từ trái sang phải như mô tả ở trên.

Ví dụ

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

5
2
0
0
0
1
3
3

Nguồn

USACO 2018 US Open Contest, Platinum — Train Tracking

Tác giả bài toán: Dhruv Rohatgi.