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
B - Thuật toán cơ bản: 04 - Mảng thống kê, đánh dấu
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.