[dwango2015_prelims_5]電波局

ID: 3381

传统题

2000ms

256MiB

尝试: 0

已通过: 0

难度: 9

上传者:

admin

标签>

3300+

問題文

ある星には正三角形の形状をした街があり、この街は $N × (N + 1) / 2$ 個の家が正三角形状に並んでいます。この正三角形は、ある辺が東西方向に平行で、その辺を構成しない頂点が最も北にある家となるような形状をしています。

各家は $2$ つの整数を用いて番号が付けられています。最も北にある家を ( $1$ , $1$ ) とし、北の端から $i$ 行目の西から $j (1 ≦ j ≦ i ≦ N)$ 番目の家には ( $i$ , $j$ ) という番号が付けられています。

以下に $N = 5$ の例を示します。

(1,

(2,

(3,

(4,

(5,

dwango 社は $M$ 個の電波局 ( $1$ から $M$ まで番号が付けられているとします) を持っており、それぞれの電波局はある正三角形状の範囲 (各辺は街の外周部の辺と平行である) にデジタルコンテンツを配信しています。

電波局 $i (1 ≦ i ≦ M)$ には $3$ つの整数 $a_i$ , $b_i$ , $c_i$ が定められており、 $1 ≦ k ≦ j ≦ c_i$ を満たすすべての整数 $j$ , $k$ に対して、家 ( $a_i+j-1$ , $b_i+k-1$ ) に配信しています。

dwango 社は新たに $1$ つ電波局を設置して、新たな顧客を呼び込もうと考えています。

電波局の設置の方法は $Q$ 通り発案されています。各設置方法に対して新たに獲得できる顧客の人数を求めるプログラムを作成してください。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $a_1$ $b_1$ $c_1$ $a_2$ $b_2$ $c_2$ : $a_M$ $b_M$ $c_M$ $Q$ $d_1$ $e_1$ $f_1$ $d_2$ $e_2$ $f_2$ : $d_Q$ $e_Q$ $f_Q$

$1$ 行目には、 $2$ つの整数 $N (1 ≦ N ≦ 1,000,000,000)$ , $M (1 ≦ M ≦ 1,000)$ が空白区切りで与えられる。
$2$ 行目から $M$ 行には、既に設置されている電波局に関する情報が与えられる。 $M$ 行のうち $i (1 ≦ i ≦ M)$ 行目には電波局 $i$ が配信する範囲を表す $3$ つの整数 $a_i$ , $b_i (1 ≦ b_i ≦ a_i ≦ N)$ , $c_i (1 ≦ c_i ≦ N-a_i+1)$ が与えられる。これは電波局 $i$ が、 $1 ≦ k ≦ j ≦ c_i$ を満たすすべての整数 $j$ , $k$ に対して、家 ( $a_i+j-1$ , $b_i+k-1$ ) に配信していることを表す。
$M + 2$ 行目には、整数 $Q (1 ≦ Q ≦ 1,000)$ が与えられる。
$M + 3$ 行目から $Q$ 行には、新たな設置方法に関する情報が与えられる。 $Q$ 行のうち $i (1 ≦ i ≦ Q)$ 行目には、 $i$ 番目の設置方法において新たに設置する電波局が配信する範囲を表す $3$ つの整数 $d_i$ , $e_i (1 ≦ e_i ≦ d_i ≦ N)$ , $f_i (1 ≦ f_i ≦ N-d_i+1)$ が与えられる。これは新たに設置する電波局が、 $1 ≦ k ≦ j ≦ f_i$ を満たすすべての整数 $j$ , $k$ に対して、家 ( $d_i+j-1$ , $e_i+k-1$ ) に配信予定であることを表す。

部分点

この問題には部分点が設定されています。

$N ≦ 200$ および $M ≦ 200$ および $Q ≦ 200$ を満たすデータセット $1$ にすべて正解すると、 $10$ 点が得られます。
$M ≦ 200$ および $Q ≦ 200$ を満たすデータセット $2$ にすべて正解すると、上記に加えてさらに $30$ 点が得られます。
追加制約のないデータセット $3$ にすべて正解すると、上記に $2$ つに加えてさらに $60$ 点が得られ、全体で $100$ 点が得られます。

出力

出力は $Q$ 行からなる。 $Q$ 行のうち $i (1 ≦ i ≦ Q)$ 行目には、 $i$ 番目の設置方法において新たに配信される家の個数を出力せよ。

入力例1

出力例1

5
2

既に設置されている $3$ つの電波局によって配信されている家の範囲は、下図のようになっています (○は配信されていることを、×は配信されいないことを表します)。

○

$1$ つ目の設置方法の場合、新たに配信される家は下図の+で示す $5$ 個です。

○

$2$ つ目の設置方法の場合、新たに配信される家は下図の+で示す $2$ 個です。

○

入力例2

出力例2


1
0
2

#dwango2015prelims5. [dwango2015_prelims_5]電波局

問題文

入力

部分点

出力

入力例1

出力例1

入力例2

出力例2

登录