“Những chú voi nhảy múa” là một buổi biểu diễn ngoạn mục ở Pattaya, với \(N\) chú voi nhảy múa trên một đường thẳng được gọi là sân khấu. Sau nhiều năm huấn luyện, các chú voi có thể thực hiện nhiều điệu múa đáng kinh ngạc. Buổi biểu diễn gồm một chuỗi tiết mục. Trong mỗi tiết mục, đúng một chú voi biểu diễn một điệu múa đáng yêu và có thể di chuyển đến một vị trí khác.

Những người tổ chức muốn làm một cuốn sách ảnh ghi lại toàn bộ buổi biểu diễn. Sau mỗi tiết mục, họ muốn chụp tất cả các chú voi theo góc nhìn của khán giả. Tại bất kỳ thời điểm nào, nhiều chú voi có thể ở cùng một vị trí; khi đó, chúng đứng sau nhau tại vị trí ấy.

Một máy ảnh có thể chụp một nhóm voi khi và chỉ khi vị trí của tất cả các chú voi trong nhóm nằm trên một đoạn thẳng có độ dài \(L\), tính cả hai đầu mút. Vì các chú voi có thể đứng rải rác trên sân khấu, có thể cần nhiều máy ảnh để đồng thời chụp được tất cả các chú voi.

Trong bài toán tương tác này, bạn phải xác định số máy ảnh ít nhất cần dùng sau mỗi tiết mục. Số máy ảnh cần dùng có thể tăng, giảm hoặc giữ nguyên giữa hai tiết mục.

Yêu cầu

Hãy cài đặt hai hàm có khai báo chính xác trong elephants.h:

void init(int N, int L, int X[]);
int update(int i, int y);

Hàm init(N,L,X) nhận số voi N, độ dài đoạn thẳng L mà một máy ảnh chụp được và mảng số nguyên một chiều X mô tả vị trí ban đầu. Các chú voi được đánh số từ \(0\) đến \(N-1\). Độ dài L là số nguyên thỏa mãn \(0 \le L \le 1\,000\,000\,000\). Với \(0 \le i < N\), chú voi \(i\) bắt đầu ở vị trí X[i]. Các vị trí ban đầu đã được sắp xếp theo thứ tự không giảm:

Trong lúc nhảy múa, thứ tự các chú voi có thể thay đổi. Hàm init chỉ được gọi một lần, trước tất cả các lần gọi update, và không trả về giá trị.

Hàm update(i,y) nhận số hiệu i của chú voi di chuyển trong tiết mục hiện tại và vị trí y của chú voi ấy sau tiết mục. Ta có \(0 \le i < N\) và y là số nguyên thỏa mãn \(0 \le y \le 1\,000\,000\,000\). Hàm được gọi nhiều lần; mỗi lần ứng với một tiết mục diễn ra tiếp sau tất cả các tiết mục trước đó. Mỗi lần gọi phải trả về số máy ảnh ít nhất cần dùng để chụp tất cả các chú voi sau tiết mục tương ứng.

Ràng buộc

Các giới hạn của \(L\), các vị trí ban đầu và các vị trí mới nêu trên áp dụng cho mọi nhóm. Nhiều chú voi được phép đứng cùng vị trí, trừ khi nhóm quy định các vị trí phải phân biệt.

Phân nhóm

Giới hạn và giao diện

Giới hạn thời gian CPU là 9 giây. Các cấu trúc chứa phần tử trong thư viện chuẩn C++ (STL) có thể chậm; đặc biệt, việc dùng chúng có thể khiến chương trình không giải được nhóm \(5\) trong thời gian cho phép. Giới hạn bộ nhớ là 256 MB. Không có giới hạn riêng cho ngăn xếp; bộ nhớ ngăn xếp được tính vào tổng bộ nhớ sử dụng.

Thư mục cài đặt là elephants/. Thí sinh cài đặt elephants.c, elephants.cpp hoặc elephants.pas. Giao diện phía thí sinh là elephants.h hoặc elephants.pas. Trình chấm mẫu là grader.c, grader.cpp hoặc grader.pas.

Dữ liệu vào

Trình chấm mẫu đọc các tệp grader.in.1, grader.in.2, ... theo định dạng:

• Dòng \(1\): \(N\), \(L\), \(M\), trong đó \(M\) là số tiết mục.
• Các dòng \(2\) đến \(N+1\): các vị trí ban đầu; dòng \(k+2\) chứa X[k], với \(0 \le k < N\).
• Các dòng \(N+2\) đến \(N+M+1\): thông tin về \(M\) tiết mục. Với \(1 \le j \le M\), dòng \(N+1+j\) chứa i[j], y[j], s[j], cách nhau bởi dấu cách. Các số này cho biết trong tiết mục \(j\), chú voi i[j] chuyển đến vị trí y[j], và số máy ảnh ít nhất cần dùng sau đó là s[j].

Dữ liệu ra

Các tệp kết quả mẫu grader.expect.1, grader.expect.2, ... đều chứa đúng dòng Correct. khi các giá trị trả về đều đúng.

Ví dụ

4 10 2
10
15
17
20
1 32 2
0 7 3

Correct.

4 10 5
10
15
17
20
2 16 1
1 25 2
3 35 2
0 38 2
2 0 3

Correct.

Nguồn

IOI 2011, ngày thi 2, Pattaya, Thái Lan. Đề Dancing Elephants, bản tiếng Anh 1.2: PDF chính thức. Nội dung được dịch từ đề chính thức; tất cả các hình minh họa đều lấy từ đề chính thức. Giao diện C/C++ và dữ liệu của trình chấm mẫu được đối chiếu với bộ API gốc.