QMATCH - Thích hợp
Giới hạn- Thời gian: 0.176s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Như một phần của chiến dịch tiếp thị, một công ty lớn ở Gdynia muốn treo logo của mình ở một số nơi trong thành phố. Công ty dành hẳn một khoản ngân sách trong năm để đầu tư tiếp thị vì vậy logo tạo ra rất hoành tráng. Giám đốc tiếp thị quyết định dùng nguyên cả dãy các tòa nhà để treo các phần của logo.
Logo bao gồm n băng treo dọc với độ dài khác nhau. Các băng được đánh số từ 1 đến n từ trái sang phải. Logo được mô tả bởi hoán vị ( s 1 , s 2 , . . ., s n ) các số tự nhiên từ 1 đến n . Băng số s 1 là ngắn nhất, băng số s 2 dài hơn hoặc bằng băng thứ s 1 nhưng ngắn hơn các băng còn lại, . . ., băng s n là dài nhất. Độ dài thực sự của các băng không phải là vấn đề đáng lưu ý.
Đường phố chính của Gdynia có m tòa nhà. Điều có thể làm cho bạn ngạc nhiên là các tòa nhà có độ cao khác nhau. Vấn đề đặt ra là tìm tất cả các vị trí có thể để treo logo.
Công ty muốn tìm dãy n tòa nhà liên tiếp nhau để treo logo. Nhà s 1 phải là thấp nhất, nhà s 2 – thấp thứ nhì, . . . Ví dụ dãy 3 nhà với các độ cao (5, 10, 4) thì dãy sắp xếp sẽ là (3, 1, 2).
Input
- Dòng đầu tiên chứa 2 số nguyên n và m (1 ≤ n ≤ m ≤ 2.10 5 )
- Dòng thứ 2 chứa n số nguyên s 1 , s 2 , . . ., s n
- Dòng thứa 3 chứa m số nguyên h i , i = 1 ÷ m (1 ≤ h i ≤ 10 9 ) – độ cao của các tòa nhà
Output
- Dòng đầu tiên chứa số nguyên k – số dãy tìm được
- Dòng thứ 2 chứa k số nguyên theo thứ tự tăng dần – số nhà đầu tiên của mỗi dãy
Example
Input: 5 10 2 1 5 3 4 5 6 3 8 12 7 1 10 11 9 Output: 2 2 6
- Người up: tohuuquan
- Nguồn bài: Thầy Nguyễn Thanh Tùng dịch từ CEOI