問題一覧 > 通常問題

No.2359 A in S ?

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 66
作問者 : 遭難者遭難者 / テスター : 👑 ygussanyygussany とりゐとりゐ
4 ProblemId : 9033 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-07-01 22:19:50

問題文

$j=1,2,\ldots,M$ に対し以下の $2$ つの条件を共に満たす $1$ 以上 $N$ 以下の整数 $i$ の個数を求めてください。

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

$A_j\equiv Y_i\pmod {X_i}$ とは

$A_j-Y_i$ が $X_i$ の倍数となることを指します。

制約

  • $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$

入力

$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$

出力

$M$ 行出力してください。

$k$ 行目 $(1\le k\le M)$ には、 $j=k$ の場合における答えを出力してください。

サンプル

サンプル1
入力
3 3
2 5 2 1
4 8 3 0
1 7 1 0
6 5 8
出力
2
2
0

$j=1$ の時、 $i=2,3$ が条件を満たします。

$j=2$ の時、 $i=1,3$ が条件を満たします。

$j=3$ の時、条件を満たす $i$ は存在しません。

サンプル2
入力
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
出力
2
3
2
2
2
0

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