trang chủ / đề bài / icpc23_mn_m

Xếp hàng chung

Đề bài

Mô tả

Hãy tưởng tượng bạn đang tổ chức một buổi biểu diễn ở trường. Bạn đã có n học sinh của nhóm A đứng thành một hàng dọc, chiều cao của các em theo thứ tự là a1,a2,…,an. Đúng lúc đó, một nhóm học sinh B gồm m em với chiều cao b1,b2,…,bm muốn tham gia vào hàng.

Vấn đề là các học sinh nhóm A muốn giữ nguyên vị trí của mình (thứ tự giữa các em không đổi), nhưng các học sinh nhóm B rất linh hoạt và có thể đứng ở bất cứ đâu: ngay đầu hàng, giữa hai học sinh bất kỳ trong hàng, hoặc ở cuối hàng.

Một lỗi được tính khi một học sinh cao hơn đứng trước một học sinh thấp hơn, tức là mỗi cặp vị trí i<j trong hàng cuối cùng mà học sinh ở vị trí i cao hơn hẳn học sinh ở vị trí j tính là một lỗi. Sau khi xếp các học sinh nhóm B vào hàng của nhóm A, số lỗi nhỏ nhất có thể là bao nhiêu?

Dữ liệu vào

Dữ liệu gồm nhiều bộ test. Dòng đầu tiên chứa số nguyên t (1≤t≤104) là số bộ test. Mỗi bộ test gồm:

  • Dòng thứ nhất chứa hai số nguyên n và m (3≤n,m≤106) là số học sinh của nhóm A và nhóm B.
  • Dòng thứ hai chứa n số nguyên a1,a2,…,an (1≤ai≤109) là chiều cao các học sinh nhóm A.
  • Dòng thứ ba chứa m số nguyên b1,b2,…,bm (1≤bi≤109) là chiều cao các học sinh nhóm B.

Dữ liệu đảm bảo tổng n của tất cả các bộ test không vượt quá 106 và tổng m của tất cả các bộ test không vượt quá 106.

Dữ liệu ra

Với mỗi bộ test, in ra một số nguyên là số lỗi nhỏ nhất có thể.

Ràng buộc

  • 1≤t≤104
  • 3≤n,m≤106
  • 1≤ai,bi≤109
  • Tổng n không vượt quá 106, tổng m không vượt quá 106.

Ví dụ

Input Output Giải thích
3
3 3
3 2 1
1 2 3
3 4
1 2 3
4 3 2 1
5 4
1 3 5 3 1
4 3 6 1
4
0
6
Bộ test thứ nhất: chẳng hạn hàng 1,3,2,1,2,3 có 4 lỗi. Bộ test thứ hai: hàng 1,1,2,2,3,3,4 không có lỗi nào. Bộ test thứ ba: chẳng hạn hàng 1,1,3,5,3,1,3,4,6 có 6 lỗi.
1
3 3
2 2 2
3 1 2
0 Xếp thành 1,2,2,2,2,3: hai học sinh cao bằng nhau đứng cạnh nhau không tính là lỗi.

Bình luận

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0