ABC462D - Accomplice

考え方

時刻と犯人 $2$ 人組のパターン数を求める問題。
「$2$ 人組を選んで、その $2$ 人での犯行数を求める」という方針では $O(N^2)$ かかるのでTLE。

ということで、時刻ごとに考えることになる。
時刻の最大値は $10^6$ なので、その長さの配列を用意するのは十分に可能。
ここに、各時刻に何人が犯行に加担可能かを記録していくことになる。
しかし、$1$ 人ずつforループで順番に $1$ を足していくと、$O(NT_{max})$ かかるのでこれもTLE。

よって、この加算を高速化する。
「vector の指定範囲に定数加算」を繰り返す場合、階差数列を作ってから累積和で復元する方法が有効。
$1$ 人ごとに vector を広く見る必要がなくなり、$O(N+T_{max})$ で完了する。

これが済んだら、時刻ごとに ${}_{加担可能人数}\mathrm{C}_2$ を求めて、その総和を答えればよい。

入力例1での動作

入力を受け取る。

n: 3
d: 2
(s,t): {(9,17), (10,12), (13,20)}

t の最大値が 20 なので、各時刻の人数データを長さ 22 で用意する。
今は階差数列になっている。

(s,t) の (9,17) を見て、$9$ 番目から $17-2=15$ 番目に $1$ を足す。

(s,t) の (10,12) を見て、$10$ 番目から $12-2=10$ 番目に $1$ を足す。

(s,t) の (13,20) を見て、$13$ 番目から $20-2=18$ 番目に $1$ を足す。

累積和をとって、本来の値にする。

${}_{各値}\mathrm{C}_2$ の総和を求める

result: 4

注意点

$N$ の値が大きいと、${}_N\mathrm{C}_2$ が大きくなり、int 型からはみ出る。
結果用変数には long long 型を用いること。

別解

シミュレーションをして答えることもできる。
その場合、以下で解ける。

• まず、館にいる時間が $D$ 未満である人は、最初からいなかったことにする。
• それ以外の人について、加担可能な時刻の開始と終了をそれぞれソートして用意する。
• 時刻を $1$ ずつ進め、人の増減をしてから $_{人数}\mathrm{C}_2$ を加算していく