COCI 2016/2017 - Contest 1 - Kraji

View as PDF

Submit solution

Points: 1.00 (partial)
Time limit: 2.0s
Memory limit: 128M
Input: stdin
Output: stdout

Suggester:
Problem source:
COCI 2016/2017 - Contest 1
Problem types
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Mirko tự xưng vua của tộc người lùn. Slavko nghe thấy vậy liền cảm thấy bị đe doạ, vì vậy anh ta ngay lập tức xưng vua của tộc yêu tinh. Bởi vì không thể có cùng một lúc hai vị vua, nên họ quyết định giải quyết vấn đề quyền hạn ngay lập tức.

Slavko dẫn ~N~ chú yêu tinh mạnh nhất, được đánh dấu từ ~1~ tới ~N~, xông tới lâu đài của Mirko. Ở trong lâu đài, họ sẽ chạm trán ~N~ người lùn mạnh nhất đang ngồi vòng tròn, được đánh dấu từ ~1~ tới ~N~ theo chiều kim đồng hồ.

Khi Slavko và binh đoàn yêu tinh bước vào lâu đài của Mirko, Mirko đã đánh dấu ~A_i~ lên mỗi chú yêu tinh của Slavko, tương ứng với số hiệu của người lùn mà chú yêu tinh đó sẽ phải chiến đấu. Tuy nhiên Mirko đã không đảm bảo rằng mỗi chú yêu tinh phải có một kẻ thù riêng biệt, và sớm sau đó một trận chiến tồi tệ đã xảy ra.

Slavko và Mirko quyết định giải quyết vấn đề theo cách sau:

  • Slavko sẽ đưa từng yêu tinh của mình vào lâu đài theo thứ tự mà anh ta chọn. Yêu tinh tiếp theo chỉ được bước vào lâu đài sau khi yêu tinh trước đó tìm được chỗ ngồi.
  • Yêu tinh có dấu ~k~ sẽ tiếp cận người lùn có dấu ~A_k~ trước. Nếu như người lùn đó chưa có ai ngồi cùng, chú yêu tinh này sẽ đến và ngồi. Còn nếu đã có yêu tinh ngồi cùng rồi, chú yêu tinh sẽ phải tiếp tục đi quanh theo chiều kim đồng hồ, cho đến khi tìm được một người lùn chưa có ai ngồi cạnh, và ngồi vào đó.

Bây giờ ~N~ cặp yêu tinh - người lùn sẽ bắt đầu cuộc chiến vật tay, và ai khoẻ hơn người đấy thắng.

Slavko đã chuẩn bị rất kĩ cho trận chiến này. Anh ta nắm rõ được sức mạnh của từng chú yêu tinh của mình. Bây giờ anh ta muốn đưa yêu tinh của mình vào lâu đài theo thứ tự đem lại nhiều chiến thắng nhất cho anh ta sau khi chúng đều tìm được chỗ ngồi.

Hãy giúp Slavko và tính toán số chiến thắng nhiều nhất mà anh ta có thể đạt được.

Input

  • Dòng đầu tiên chứa số nguyên ~N~ ~(1 ≤ N ≤ 5\cdot 10^{5})~.
  • Dòng thứ hai chứa ~N~ số nguyên ~A_i~ ~(1 ≤ A_i ≤ N)~, đối thủ mà Mirko chọn.
  • Dòng thứ ba chứa ~N~ số nguyên ~P_i~ ~(1 ≤ P_i ≤ 10^{9})~, đại diện cho sức mạnh của từng người lùn.
  • Dòng thứ tư chứa ~N~ số nguyên ~V_i~ ~(1 ≤ V_i ≤ 10^{9})~, đại diện cho sức mạnh của từng yêu tinh.

Dữ liệu đảm bảo sức mạnh của người lùn và yêu tinh đôi một khác nhau.

Output

  • In ra số chiến thắng nhiều nhất mà Slavko có thể đạt được.

Sample Input 1

3
2 3 3
4 1 10
2 7 3

Sample Output 1

2

Sample Input 2

4
3 1 3 3
5 8 7 10
4 1 2 6

Sample Output 2

1

Sample Input 3

3
1 2 3
8 4 3
9 2 6

Sample Output 3

2

Giải thích ví dụ 1

Slavko có thể sắp xếp số yêu tinh theo thứ tự: ~3~, ~2~, ~1~. Theo cách này, yêu tinh số ~3~ sẽ ngồi cạnh người lùn số ~3~, yêu tinh số ~2~ sẽ phải dịch một ghế theo chiều kim đồng hồ và ngồi cạnh người lùn số ~1~, và yêu tinh số ~2~ sẽ ngồi cạnh người lùn số ~2~. Yêu tinh số ~1~, ~2~ sẽ thắng khi giao đấu, và yêu tinh số ~3~ sẽ thua.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.