USACO 2025 - Cow Checkups

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Dạng bài
Ngôn ngữ cho phép
Assembly, Awk, C, C#, C++, Clang, Cobol, D, Groovy, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, Swift
Điểm: 2300 (p) Thời gian: 4.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

\(N\) (\(1 \leq N \leq 5 \cdot 10^5\)) con bò của Farmer John đang đứng thành một hàng, với bò \(1\) ở đầu hàng và bò \(N\) ở cuối hàng. Các con bò của FJ cũng thuộc nhiều loài khác nhau. Ông ký hiệu mỗi loài bằng một số nguyên từ \(1\) đến \(N\). Con bò thứ \(i\) tính từ đầu hàng thuộc loài \(a_i\) (\(1 \leq a_i \leq N\)).

FJ đang đưa đàn bò đến khám tại một bệnh viện bò địa phương. Tuy nhiên, bác sĩ thú y cho bò rất kén chọn và chỉ muốn khám con bò thứ \(i\) trong hàng nếu nó thuộc loài \(b_i\) (\(1 \leq b_i \leq N\)).

FJ lười biếng và không muốn sắp xếp lại hoàn toàn đàn bò. Ông sẽ thực hiện thao tác sau đúng một lần.

  • Chọn hai số nguyên \(l\) và \(r\) sao cho \(1 \leq l \le r \leq N\). Đảo ngược thứ tự các con bò nằm giữa con bò thứ \(l\) và con bò thứ \(r\) trong hàng, tính cả hai đầu.

FJ muốn đo lường mức độ hiệu quả của cách làm này. Hãy tìm tổng số con bò được bác sĩ thú y khám trên tất cả \(N(N+1)/2\) thao tác có thể.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(N\).

Dòng thứ hai chứa \(a_1, a_2, \ldots, a_N\).

Dòng thứ ba chứa \(b_1, b_2, \ldots, b_N\).

Dữ liệu ra

In một dòng chứa tổng số con bò được bác sĩ thú y khám trên tất cả các thao tác có thể.

Ví dụ

Ví dụ 1

Input 
3
1 3 2
3 2 1
Output 
3
Giải thích

Nếu FJ chọn \((l=1,r=1)\), \((l=2,r=2)\) hoặc \((l=3,r=3)\) thì không có con bò nào được khám. Lưu ý rằng các thao tác này không thay đổi vị trí của các con bò.

Các thao tác sau khiến một con bò được khám:

  • \(l=1,r=2\): FJ đảo thứ tự con bò thứ nhất và thứ hai, nên loài của các con bò trong hàng mới là \([3,1,2]\). Con bò thứ nhất sẽ được khám.
  • \(l=2,r=3\): FJ đảo thứ tự con bò thứ hai và thứ ba, nên loài của các con bò trong hàng mới là \([1,2,3]\). Con bò thứ hai sẽ được khám.
  • \(l=1,r=3\): FJ đảo thứ tự con bò thứ nhất, thứ hai và thứ ba, nên loài của các con bò trong hàng mới là \([2,3,1]\). Con bò thứ ba sẽ được khám.

Tổng số con bò được khám trên cả sáu thao tác là \(0+0+0+1+1+1=3\).

Ví dụ 2

Input 
3
1 2 3
1 2 3
Output 
12
Giải thích

Có ba thao tác có thể khiến \(3\) con bò được khám: \((l=1,r=1)\), \((l=2,r=2)\) và \((l=3,r=3)\). Mỗi thao tác còn lại đều khiến \(1\) con bò được khám. Tổng số con bò được khám trên cả sáu thao tác là \(3+3+3+1+1+1=12\).

Ví dụ 3

Input 
7
1 3 2 2 1 3 2
3 2 2 1 2 3 1
Output 
60

Phân nhóm

  • Input 4: \(N\le 100\).
  • Input 5: \(N\le 5000\).
  • Inputs 6-9: \(a_i, b_i\) đều được sinh ngẫu nhiên đều trong đoạn \([1,N]\).
  • Inputs 10-15: \(a_i, b_i\) đều được sinh ngẫu nhiên đều trong đoạn \([1,2]\).
  • Inputs 16-23: Không có ràng buộc bổ sung.

Nguồn

USACO 2025 January Contest, Silver — Cow Checkups

Đề bài: https://usaco.org/index.php?page=viewproblem2&cpid=1470

Tác giả đề: Chongtian Ma, Haokai Ma và Alex Liang

Bình luận

Mới nhất
Tải bình luận...

Không có bình luận nào.

Kỳ thi: