問題一覧 > 通常問題

No.2359 A in S ?

レベル : / AI推定難易度 : 1800 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 70
作問者 : 👑 qand / テスター : ygussany とりゐ
お気に入りにしたユーザー ProblemId : 9033 / 自分の提出
問題文最終更新日: 2023-07-01 22:19:50
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 394 (順位表) の他の問題:

Problem Statement

For each $j=1,2,\ldots,M$, find the number of integers $i$ between $1$ and $N$, inclusive, that satisfy both of the following $2$ conditions.

  • $L_i\le A_j \le R_i$
  • $A_j\equiv Y_i\pmod {X_i}$

What $A_j\equiv Y_i\pmod {X_i}$ means

It means that $A_j-Y_i$ is a multiple of $X_i$.

Constraints

  • $1\le N\le 10^5$
  • $1\le L_i\le R_i\le 10^5$
  • $0\le Y_i < X_i \le 10^5$
  • $1\le M\le 10^5$
  • $1\le A_j\le 10^5$

Input

$N$ $M$
$L_1$ $R_1$ $X_1$ $Y_1$
$L_2$ $R_2$ $X_2$ $Y_2$
$\vdots$
$L_N$ $R_N$ $X_N$ $Y_N$
$A_1$ $A_2$ $\ldots$ $A_M$

Output

Output $M$ lines.

On the $k$-th line $(1\le k\le M)$, output the answer for the case $j=k$.

Sample

Sample 1
Input
3 3
2 5 2 1
4 8 3 0
1 7 1 0
6 5 8
Output
2
2
0

When $j=1$, $i=2,3$ satisfy the conditions.

When $j=2$, $i=1,3$ satisfy the conditions.

When $j=3$, no $i$ satisfies the conditions.

Sample 2
Input
5 6
1 5 2 0
1 5 2 1
1 5 7 2
1 5 1 0
1 5 100 55
1 2 3 4 5 55
Output
2
3
2
2
2
0

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。