Đường hầm (TUNNER-11QB2020)

Xem dạng PDF

Gửi bài giải

Điểm: 10,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: TUNNER.INP
Output: TUNNER.OUT

Dạng bài
Ngôn ngữ cho phép
C, C++, C++ (Themis), Java, Pascal, Python, Scratch

Trên đường quốc lộ, có ~n~ xe ô tô đi qua đường hầm một chiều. Các xe ô tô được đánh số từ ~1~ đến ~n~, mỗi xe đi vào và đi ra đường hầm với tốc độ không đổi. Ở đầu đường hầm và cuối đường hầm đều được gắn camera an ninh. Nhờ các camera an ninh mà cảnh sát giao thông biết được thứ tự các xe ô tô đi vào và ra khỏi đường hầm. Quy định giao thông nghiêm cấm các xe vượt nhau trong đường hầm. Nếu một xe i vượt một xe j trong đường hầm thì xe i sẽ bị phạt. Mỗi xe sẽ bị xử phạt một lần khi ra khỏi đường hầm nếu vượt bất kỳ một xe nào khác ở trong đường hầm. Xe i chắc chắn đã vượt xe j nếu xe i vào đường hầm sau xe j và đi ra khỏi đường hầm trước xe j.

Yêu cầu: Cho biết thứ tự đi vào và đi ra khỏi đường hầm của ~n~ xe ô tô, hãy đếm số lượng các xe bị phạt.

Dữ liệu vào:

Cho trong tệp văn bản TUNNEL.INP có cấu trúc như sau:

  • Dòng 1: Ghi số nguyên dương ~n~ là số lượng xe đi qua đường hầm.
  • Dòng 2: Ghi ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ là thứ tự đi vào của các xe.
  • Dòng 3: Ghi ~n~ số nguyên dương ~b_1, b_2, \dots, b_n~ là thứ tự đi ra của các xe.
Dữ liệu ra:

Ghi ra tệp văn bản TUNNEL.OUT theo cấu trúc:

  • Dòng 1: ghi kết quả tìm được tương ứng với dữ liệu vào.
Ví dụ:

Input: TUNNEL.INP

5
3 5 2 1 4
4 3 2 5 1

Output: TUNNEL.OUT

2

Giải thích:

  • Xe 4 vượt các xe: 1, 2, 3, 5 nên xe 4 bị phạt
  • Xe 2 vượt 5 nên xe 2 bị phạt
Ràng buộc:

~(2 \leq n \leq 10^5; 1 \leq a_i, b_i \leq n; 1 \leq i \leq n)~.


Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.