問題一覧 > 通常問題

No.1679 マスゲーム

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 34
作問者 : aspiaspi / テスター : NatsubiSoganNatsubiSogan
0 ProblemId : 6994 / 自分の提出
問題文最終更新日: 2021-09-11 17:46:03

問題文

二次元平面上に $N$ 個の点があります。それぞれの点は、赤・青いずれかの色で塗られています。

現在の時刻を $0$ として、点が平面上を移動します。$i$ $(1 \leq i \leq N)$ 番目の点は以下のように動きます。

  • $A_i=0$ のとき:$i$ 番目の点の色は赤です。時刻 $T_i$ に 座標 $(B_i, 0)$ を出発し、$1$ 単位時間で $y$ 軸正方向に $1$ 移動します。
  • $A_i=1$ のとき:$i$ 番目の点の色は青です。時刻 $T_i$ に 座標 $(0, B_i)$ を出発し、$1$ 単位時間で $x$ 軸正方向に $1$ 移動します。

赤い点と青い点がぶつかる回数を求めてください。つまり、赤い点と青い点の組であって、両者がある時刻 $t$ において同じ座標に存在するようなものの数を求めてください。

入力

$N$
$A_1$ $B_1$ $T_1$
$A_2$ $B_2$ $T_2$
$\vdots$
$A_N$ $B_N$ $T_N$
  • $1 \leq N \leq 2 \times 10^{5}$
  • $A_i \in \{0,1\}$
  • $1 \leq B_i \leq 2 \times 10^{5}$
  • $0 \leq T_i \leq 2 \times 10^{5}$
  • 入力はすべて整数

出力

赤い点と青い点がぶつかる回数を一行に出力してください。

サンプル

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

赤い点と青い点がぶつかるのは、以下の $2$ 回のみです。

  • 時刻 $5$ に、点 $1,2$ が 座標 $(1,2)$ でぶつかる。
  • 時刻 $6$ に、点 $3,4$ が 座標 $(5,5)$ でぶつかる。
サンプル2
入力
5
0 1 2
0 1 2
1 1 3
1 1 3
1 1 3
出力
0

赤い点と青い点が $1$ 回もぶつからないこともあります。同じ座標から複数の点が出発する場合があることに注意してください。

サンプル3
入力
6
0 1 5
0 5 9
0 8 2
0 1 0
0 100 200
0 200000 200000
出力
0

全て同じ色なので、明らかに $1$ 回もぶつかりません。

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