Counting Digits 1

Points 100 0.25s 256M

You are given a sequence of \(N\) positive integers \(a_1, a_2, \ldots, a_N\). Then you receive \(Q\) queries; the \(i\)-th query provides a positive integer \(b_i\), and you must report how many times \(b_i\) appears in the sequence \(a\).

The following sample program scores only 2 points:

#include<iostream>
using namespace std;
const int MAX_N = 200000;
int main() {
    int a[MAX_N];
    int N;
    cin >> N;
    for(int i = 0; i < N; i++) cin >> a[i];
    int Q;
    cin >> Q;
    while(Q--) {
        int b;
        cin >> b;
        int ans = 0;
        for(int i = 0; i < N; i++) ans += (a[i] == b);
        cout << ans << endl;
    }
    return 0;
}

Input

The first line contains a positive integer \(N\) (\(N \le 2 \times 10^5\)). The second line contains \(N\) positive integers \(a_1, a_2, \ldots, a_N\) (\(1 \le a_i \le 10^6\)).

The third line contains a positive integer \(Q\) (\(1 \le Q \le 2 \times 10^5\)). The fourth line contains \(Q\) positive integers \(b_1, b_2, \ldots, b_Q\) (\(1 \le b_i \le 10^9\)).

Output

Print \(Q\) lines; the \(i\)-th line should contain the answer for the \(i\)-th query.

Scoring

There are three subtasks. Each subtask contains multiple test cases, and you earn the subtask's score only if you solve all of its tests.

  • Subtask \(1\) (40 points): \(N, Q \le 5000\), \(b_i \le 10^6\).
  • Subtask \(2\) (40 points): \(b_i \le 10^6\).
  • Subtask \(3\) (20 points): no additional constraints.

Sample Input 1

5
1 3 1 4 520
7
1 2 3 4 100000 1000000000 7

Sample Output 1

2
0
1
1
0
0
0

Note

To highlight that arrays are faster than map in the STL, the time limit is set to 0.25 seconds.

To pass the problem, enable fast I/O before reading anything:

cin.tie(0);
ios_base::sync_with_stdio(false);

Always use \n for newlines; using endl will also be too slow.

Problem page help

Keyboard shortcuts

Main features

  • Sample tests — Runs the sample cases bundled with the problem and auto-compares against the expected output.
  • Custom test — Run your code with your own stdin. Optionally tick the "Compare with expected (diff)" box to verify against expected output line-by-line.
  • Template — Paste the default code template you set on your profile page.
  • Collab — Edit this problem together with classmates in real time.
  • Auto-draft — Editor contents auto-save to your browser every 1.5 seconds (per account / problem / language).
  • Submit — Send your code to the judge for grading; returns AC / WA / TLE etc.

Limits

  • Source code: at most 65,536 characters
  • Custom test stdin and expected output: at most 1 MB each (≈1 million characters)
  • Custom test and sample test share the sandbox; about 1 request per 3 s per user (sample test: 1 per 1 s)
  • Custom test and sample test both have a 15 second wall-clock cap (the official judge still uses the problem time limit)
  • Interactive problems do not offer custom test (cannot simulate interaction with the judge).
  • Submitting has no rate limit, but rapid repeated submissions on the same problem are treated as score farming.