[Buổi 7][Hai con trỏ & Cửa sổ trượt][HW] Bài 3: Chuỗi sự kiện không lặp dài nhất
Chuỗi sự kiện không lặp dài nhất
Bối cảnh và bài toán
Một luồng sự kiện ghi lại ID theo thời gian. Đội phân tích cần tìm khoảng liên tiếp dài nhất mà không ID nào xuất hiện hai lần — một khoảng "không lặp" hoàn toàn.
Yêu cầu
Tìm độ dài đoạn liên tiếp dài nhất có tất cả giá trị đôi một khác nhau.
Input
- Dòng 1:
n. - Dòng 2:
nID.
Output
In độ dài lớn nhất.
Ràng buộc
1 <= n <= 2 * 10^51 <= id[i] <= 10^9
Chấm điểm
| Subtask | Điểm | Điều kiện | Official tests |
|---|---|---|---|
| S1 | 20% | n ≤ 200 | 01–04 |
| S2 | 30% | n ≤ 5*10^4 | 05–10 |
| S3 | 50% | Không có ràng buộc bổ sung | 11–20 |
Ví dụ 1
Input
8
1 2 1 3 2 7 4 2
Output
5
Giải thích. Đoạn 1 3 2 7 4 (vị trí 3..7) có 5 ID phân biệt.
Ví dụ 2
Input
6
5 5 5 5 5 5
Output
1
Giải thích. Bất kỳ đoạn dài hơn 1 đều lặp ID 5.
Thông tin bài tập
| Thuộc tính | Giá trị |
|---|---|
| Mã bài | DSA-M03-B07-HW03 |
| Buổi | B07 |
| Loại bài | HOMEWORK |
| Mức độ khó | Trung bình (Medium) |
| Thời gian làm bài khuyến nghị | 45 phút |
| Time limit | 2 giây |
| Memory limit | 256 MB |
| Tổng điểm | 100 |
| Chuẩn ngôn ngữ tham chiếu | C++17 |
Nguồn: Phỏng theo CSES Problem Set — Playlist (Task 1141).
Tham khảo: https://cses.fi/problemset/task/1141/
Comments