minict12

Tác giả:

Dạng bài

Điểm: 300 (p) Thời gian: 1.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

Cho mảng \(A\) gồm \(n\) số nguyên. Một đoạn con liên tục của mảng \(A\) là một hoặc nhiều phần từ liên tục lấy tử mảng \(A\). Một đoạn con liên tục được gọi là hoàn hảo nếu như nó chứa không nhiều hơn \(k\) số nguyên khác nhau.

Yêu cầu

Hãy tìm đoạn con liên tục hoàn hảo dài nhất của mảng \(A\).

Input

Dòng đầu tiên là hai số nguyên dương \(n\), \(k\) (\(1 \leq k \leq n \leq 5*10^5\)).
Dòng thứ hai là một dãy số nguyên \(A_1, A_2, ..., A_n\) (\(0 \leq A_i \leq 10^6\)).

Output

In ra hai số nguyên \(l, r\) (\(1 \leq l \leq r \leq n\)) - chỉ số bắt đầu và chỉ số kết thúc của đoạn con liên tục hoàn hảo dài nhất. Nếu như có nhiều đoạn con dài nhất, in ra đoạn con có chỉ số \(l\) nhỏ nhất.

Scoring

Subtask \(1\) (\(50\%\) số điểm): \(n \le 100\).
Subtask \(2\) (\(50\%\) số điểm): không có điều kiện gì thêm

Example

Test 1

Input

3 2
1 2 3

Output

1 2

Note

Bình luận

3
longkold00 10:01 p.m. 13 Tháng 10, 2021 ← đã chỉnh sửa →
Mình sẽ chia sẻ cách sử dụng thao tác 2 con trỏ + đếm phân phối của mình nhé:

Gọi res là số phần tử khác nhau của dãy đang xét,l là độ dài lớn nhất của dãy hoàn hảo tìm đc. i=1 và j=2. Nếu ai != aj gán res=2 ngược lại res=1.

Ta sử dụng 1 mảng m để đếm số lần xuất hiện của phần tử.

trong khi j<=n ta sẽ xét 2 th:

3.1
Nếu res<=k: kiểm tra xem độ dài dãy hiện tại có lớn hơn l hay không. Nếu có ta gán 2 biến head=i và tail =j;
Gán j++ và kt xem m[aj]==1 hay không (tức là aj có phải là phần tử mới xuất hiện hay không) nếu có thì res++;

3.2
Nếu res>k: ta giảm m[ai] 1 đơn vị (loại pt ở vị trí i). Sử dụng vòng while kt nếu m[ai]!=0 (tức là vẫn tồn tại ak=ai (i<k<=j) thì i++ và m[ai]--
Gán i++ (bù cho m[ai] ta giảm ban đầu) và res-- (ta loại 1 phần tử riêng biệt ra khỏi dãy)

0

VoBaThongL921 7:52 a.m. 14 Tháng 10, 2021

hay quá anh ơi, nhờ anh hướng dẫn mà em ac đc rùi :v

0

longkold00 7:49 p.m. 14 Tháng 10, 2021

quên a không bảo e, em có thể dùng kiểu dữ liệu struct để dễ quản lý các bài có nhiều ai,bi,ci. Dùng hàm bool ss(kiểu dl + s1,kiểu dl + s2) {return s1.second<s2.second}; thể định nghĩa hàm sort(a+1,a+1+n,ss) sắp xếp theo ý muốn nhé. còn mặc định hàm sort sẽ sắp xếp .first

0

longkold00 7:43 p.m. 14 Tháng 10, 2021

:v nay a tha hóa cả ngày chơi game :> nên giờ mới vô

0

VoBaThongL921 8:08 p.m. 14 Tháng 10, 2021

ơ em tưởng anh hôm nay bận học bài:) em chơi lỡ chơi game lúc học online xong mai cô kiểm tra 15 phút làm em bối rối quá UwU

0

longkold00 8:55 p.m. 14 Tháng 10, 2021

giờ a đang lag :V chắc đi học tiếng anh rồi chiều mai code :>

0

VoBaThongL921 9:00 p.m. 14 Tháng 10, 2021

vâng bye anh

0

longkold00 8:53 p.m. 14 Tháng 10, 2021

sáng nay bọn a chỉ nhận lớp quốc phòng nên nghỉ sớm, mai mới học :>

3 bình luận nữa