Tuyển sinh 10 chuyên Vĩnh Phúc 2024 - Câu 3 - Thống kê
Point: 100.0
Time limit: 1.0s
Memory limit: 1 G
Input: stdin
Output: stdout
Author:  
Problem type
Ngôn ngữ cho phép
C, C#, C++, Pascal, Python

Thống kê

Cho hai dãy số nguyên cùng độ dài, \(A = (a_1, a_2, ..., a_n); B = (b_1, b_2, ..., b_n\)). Hãy trả lời \(Q\) truy vấn, truy vấn thứ \(i (1 ≤ i ≤ Q)\) có tham số \(k_i\) và yêu cầu xác định các giá trị \(x_i, y_i\), trong đó:

  • \(x_i\): là số lượng giá trị có số lần xuất hiện trong dãy \(A\) lớn hơn hay bằng \(k_i\).
  • \(y_i\): là số lượng giá trị có số lần xuất hiện trong dãy \(B\) lớn hơn hay bằng \(k_i\).

Dữ liệu:

  • Dòng 1: hai số nguyên dương \(n, Q (1 \leq n \leq 10^6; 1 \leq Q \leq 10^6)\);
  • Dòng 2: \(n\) số nguyên \(a_1, a_2, ..., a_n (|a_i| \leq 10^6)\);
  • Dòng 3: \(n\) số nguyên \(b_1, b_2, ..., b_n (|b_i| \leq 10^6);\)
  • Dòng 4: \(Q\) số nguyên dương \(k_1, k_2, ..., k_Q (1 \leq k_i \leq n).\)

Kết quả:

  • Dòng \(1 ... Q\): dòng \(i (1 \leq i \leq Q)\) ghi hai số nguyên \(x_i, y_i\).

Ví dụ:

Input Output Giải thích
7 2 3 3 Các giá trị xuất hiện ít nhất 2 lần trong dãy A: 1 3 4; trong dãy B: 1 3 5.
1 1 3 2 3 4 4 4 3 Các giá trị xuất hiện ít nhất 1 lần trong dãy A: 1 2 3 4; trong dãy B: 1 3 5.
1 1 5 3 5 3 3
2 1

Ràng buộc:

  • Có 30% điểm ứng với các test thỏa mãn \(n ≤ 1000; Q = 1; 0 \leq a_i, b_i \leq 1000;\)
  • Có 30% điểm ứng với các test thỏa mãn \(n, Q \leq 1000; 0 \leq a_i, b_i \leq 1000;\)
  • 40% số điểm còn lại không có ràng buộc bổ sung.