TS10 Lâm Đồng 2026 - Đếm số

Xem dạng PDF
Gửi bài giải
Điểm: 14,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout
Tác giả:
clue_
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Output Only, Pascal, PyPy, Python, Scratch, TEXT

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Cho dãy ~a~ gồm ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ và dãy ~b~ gồm ~m~ số nguyên dương ~b_1, b_2, \dots, b_m~.

Yêu cầu: Trong ~m~ số nguyên dương ~b_1, b_2, \dots, b_m~ ~(1 \le j \le m)~ tương ứng với mỗi số nguyên dương ~b_j~, hãy đếm xem có bao nhiêu số nguyên dương nhỏ hơn ~b_j~ không xuất hiện trong dãy ~a~.

Input

  • Dòng đầu tiên chứa hai số nguyên dương ~n, m~ lần lượt là số lượng phần tử của dãy ~a~ và dãy ~b~ ~(1 \le n \le 10^5, 1 \le m \le 10^6)~.

  • Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ ~(1 \le a_i \le 10^9)~.

  • Dòng thứ ba chứa ~m~ số nguyên dương ~b_1, b_2, \dots, b_m~ ~(1 \le b_j \le 10^9)~.

Output

Gồm ~m~ dòng, dòng thứ ~j~ chứa một số nguyên duy nhất là số lượng số nguyên dương nhỏ hơn ~b_j~ không xuất hiện trong dãy ~a~.

Scoring

Subtask Điểm Ràng buộc
1 ~30\%~ ~m = 1, a_i \le 10^5~
2 ~30\%~ ~m = 1, a_i \le 10^9~
3 ~40\%~ Không có ràng buộc gì thêm

Sample Input 1

5 2
1 4 2 7 8
6 8

Sample Output 1

2
3

Notes

  • Các số nguyên nhỏ hơn ~6~ không xuất hiện trong dãy ~a~ là ~3~ và ~5~.

  • Các số nguyên nhỏ hơn ~8~ không xuất hiện trong dãy ~a~ là ~3, 5~ và ~6~.

Bình luận

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


  • 0
    lhuy18322  đã bình luận lúc 31, Tháng 8, 2026, 13:15

    cho xin code


    • 0
      BaoNGQT2013ok  đã bình luận lúc 8, Tháng 9, 2026, 12:18

      include <bits/stdc++.h>

      using namespace std;

      struct Q { long long x; int id; };

      bool cmp(Q a, Q b) { return a.x < b.x; }

      int main() { ios::syncwithstdio(false); cin.tie(NULL);

      int n, m;
cin >> n >> m;

vector&lt;long long> a(n);
vector<Q> b(m);

for (int i = 0; i < n; i++)
    cin >> a[i];

for (int i = 0; i < m; i++) {
    cin >> b[i].x;
    b[i].id = i;
}

sort(a.begin(), a.end());
sort(b.begin(), b.end(), cmp);

vector&lt;long long> ans(m);

int j = 0;
long long dem = 0;

for (int i = 0; i < m; i++) {
    while (j < n && a[j] < b[i].x) {
        if (j == 0 || a[j] != a[j - 1])
            dem++;
        j++;
    }

    ans[b[i].id] = b[i].x - 1 - dem;
}

for (int i = 0; i < m; i++)
    cout << ans[i] << '\n';

return 0;

      }


  • -5
    Tung_skibidi  đã bình luận lúc 22, Tháng 8, 2026, 1:46

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • -2
      nguyenthinh03082015  đã bình luận lúc 6, Tháng 9, 2026, 3:21

      cc ba may hoc nqu hon oc cho


      • -2
        Tung_skibidi  đã bình luận lúc 6, Tháng 9, 2026, 3:23

        ai hỏi