Mã bài:
party1
Điểm:
2,5 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
512M
Dữ liệu vào:
stdin
Dữ liệu ra:
stdout
Tác giả:
Dạng bài
Nhân dịp tết đến bạn Tèo muốn mời các bạn của mình dự một buổi liên hoan cuối năm. Tèo có ~n~ người bạn được đánh số từ ~1~ tới ~n~, bạn thứ ~i~ tổng tài sản là ~i~, tổng tài sản càng lớn thì càng giàu.
Để mời được người bạn thứ ~i~ ~(1 \le i \le n)~ thì phải thỏa ~2~ điều kiện:
- Trong bữa tiệc có nhiều nhất ~a_i~ người giàu hơn bạn thứ ~i~.
- Trong bữa tiệc có nhiều nhất ~b_i~ người không giàu bằng bạn thứ ~i~.
Tèo luôn muốn buổi tiệc đông vui nhất có thể, các lập trình viên ở CLAOJ
hãy giúp Tèo tính xem Tèo có thể mời được tối đa bao nhiêu người bạn nhé.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên dương ~n~ ~(1 \le n \le 2\times10^5)~ là số người bạn của Tèo.
- Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(0 \le a_i \le n)~.
- Dòng thứ ba chứa ~n~ số nguyên ~b_1, b_2, \dots, b_n~ ~(0 \le b_i \le n)~.
Kết quả ra
- Một dòng duy nhất chứa số người tối đa có thể được mời đến buổi tiệc.
Ràng buộc
- Có ~30\%~ số test ứng với ~1 \le n \le 20~.
- Có ~20\%~ số test ứng với ~1 \le n \le 2\times 10^5, a_i = n~.
- Có ~20\%~ số test ứng với ~1 \le n \le 2\times 10^5, b_i = n~.
- Có ~10\%~ số test ứng với ~1 \le n \le 5000~.
- Còn lại ~20\%~ số test không có ràng buộc gì thêm.
Ví dụ
Dữ liệu vào
4
0 3 2 1
1 2 0 3
Dữ liệu ra
2
Giải thích
Có nhiều cách chọn, một cách chọn hợp lệ là:
- Bạn số ~2~ và ~4~ là những bạn được mời đến buổi tiệc.
- Bạn số ~2~ thỏa điều kiện vì trong các bạn được mời chỉ có ~1~ bạn giàu hơn ~(1 < a_2)~ và không có bạn nào không giàu bằng ~(0 < b_2)~.
- Bạn số ~4~ thỏa điều kiện vì trong các bạn được mời không có bạn nào giàu hơn ~(0 < a_4)~ và chỉ có ~1~ bạn không giàu bằng ~(1 < b_4)~.
Bình luận