Bedao Regular Contest 10 - VOLUNTEERS

View as PDF

Submit solution


Points: 0.20 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Đợt tuyển tình nguyện viên lần thứ ~2~ của VNOI đã diễn ra thành công và tốt đẹp. Những TNV được chọn ra đều là những gương mặt ưu tú nhất, để kiểm tra khả năng của TNV, các admin đã chuẩn bị một bài kiểm tra như sau:

Admin có ~n~ công việc, các công việc được đánh số từ ~1~ đến ~n~ tương ứng với độ khó lần lượt ~a_1, a_2, a_3, \dots, a_n~. Có ~m~ tình nguyện viên, mỗi tình nguyện viên cũng được đánh số từ ~1~ đến ~m~ tương ứng với khả năng làm được công việc độ khó lần lượt là ~b_1, b_2, b_3, \dots, b_m~. Các TNV đều là những người hăng hái ai cũng muốn chọn công việc có độ khó cao nhất (nhưng không vượt quá khả năng của mình) . Các TNV lần lượt từ trái sang phải đi nhận từng công việc, mỗi công việc chỉ được chọn ~1~ lần , nếu không có công việc nào phù hợp với khả năng của mình thì TNV đó sẽ được nghỉ.

Sau ~m~ lượt, có thể còn lại những công việc không được chọn bởi ai cả, nhiệm vụ của bạn là tìm công việc có độ khó cao nhất, nếu không còn lại công việc nào thì in ra ~-1~.

Input

Gồm ~3~ dòng chứa ~2~ số nguyên ~n~ và ~m~ ~(1 \le n, m \le 10^{6})~.

Dòng thứ hai gồm ~n~ số nguyên dương ~a_1, a_2, a_3, \dots, a_n~ ~(1 \le a_i \le 10^{9})~ tương ứng là độ khó của từng công việc.

Dòng thứ ba gồm ~m~ số nguyên dương ~b_1, b_2, b_3, \dots, b_m~ ~(1 \le b_i \le 10^{9})~ tương ứng là năng lực của từng TNV.

Output

Gồm một số nguyên duy nhất là yêu cầu của bài toán.

Subtask

  • ~20\%~ số test có ~1 \le a_i \le 5000~
  • ~80\%~ số test còn lại không có điều kiện gì thêm

Sample Input

4 6
1 8 2 4
3 3 6 1 5 2

Sample Output

8

Note

Quy trình chọn việc từ trái qua phải như sau :

  • Người ~1~ có khả năng làm công việc có độ khó cao nhất là ~3~ chọn công việc thứ ~3~ có độ khó cao nhất nhưng không vượt quá khả năng của mình ~(2 \le 3)~ , loại công việc thứ ~3~ ra khỏi danh sách.

Danh sách công việc còn lại có thể chọn là ~[1, 8, 4]~.

  • Người ~2~ có khả năng làm công việc có độ khó cao nhất là ~3~ chọn công việc thứ ~1~ có độ khó cao nhất nhưng không vượt quá khả năng của mình ~(1 \le 3)~ , loại công việc thứ ~1~ ra khỏi danh sách.

Danh sách công việc còn lại có thể chọn là ~[8, 4]~.

  • Người ~3~ có khả năng làm công việc có độ khó cao nhất là ~6~ chọn công việc thứ ~4~ có độ khó cao nhất nhưng không vượt quá khả năng của mình ~(4 \le 6)~ , loại công việc thứ ~4~ ra khỏi danh sách.

Danh sách công việc còn lại có thể chọn là ~[8]~.

  • Ba người còn lại không thể chọn được công việc nào vì công việc có thể chọn còn lại vượt quá khả năng của ~3~ người đó.

Vậy công việc lớn nhất còn lại là ~8~.


Comments

Please read the guidelines before commenting.



  • 0
    dunghlorp   commented on Oct. 5, 2022, 8:54 p.m. edit 2

    anh em giải thích giúp mình với sao lại bị runtime với segmentation error nhỉ


  • 3
    CBNK28_XUANTHAO   commented on Sept. 28, 2022, 11:40 p.m.

    Cách giải khác với cách giải của admin và đơn giản hơn nhiều.

    đầu tiên , ta sắp xếp lại 2 mảng a và b theo thứ tự giảm dần .

    xét từ 1 đến min(n,m) , tại vị trí đầu tiên mà a[i] > b[i] thì kết quả bài toán sẽ là a[i] . Các bạn có thể chứng minh tính chính xác của thuật toán này nha :3


    • -1
      nguyenhuunhan   commented on Sept. 30, 2022, 7:12 p.m.

      nhưng nếu làm thế thì độ phức tạp sẽ là o(n log n+m log m) nên tất nhiên là cách làm của ad vẫn hay hơn rồi


  • -6
    aRandomGuy   commented on Sept. 26, 2022, 2:40 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.