No.2359 A in S ?

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 66
作問者 :

遭難者 / テスター : 👑

ygussany

とりゐ

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

入力

出力

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

出力

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