시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 0 | 0 | 0 | 0.000% |
We are given a set A of positive integers. For a given sequence of digits x, we would like to know how many times it occurs, as a fragment (i.e., a contiguous part), in the numbers from the set A. Note that a sequence x may occur as a fragment of a given a ∈ A multiple times - then we are interested in all its occurrences.
The first line of the standard input contains two integers n and m (1 ≤ n ≤ 5 000, 1 ≤ m ≤ 500 000) representing the number of lines containing a description of the set A and the number of sequences of digits denoting the queries. Each of the following n lines contains two integers ai and bi. These numbers satisfy the following inequalities: 1 ≤ a1 ≤ b1 < a2 ≤ b2 < a3 ≤ b3 < ... < an ≤ bn ≤ 1018 and represent the following set: A = [a1,b1] ∪ [a2,b2] ∪ [a3,b3] ∪ ... ∪ [an,bn].
Each of the following m lines contains a sequence of digits xj consisting of at least 1 and at most 19 digits 0..9.
Your program should write m lines to the standard output. The i-th of these lines should contain a single integer: the total number of occurrences of xj in all numbers from the set A, including multiple occurrences in respective elements of A.
1 3 2220 2223 222 0 07
5 1 0
Contest > Algorithmic Engagements > PA 2010 3-1번