問題一覧 > 通常問題

No.1679 Mass Game

レベル : / AI推定難易度 : 800 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 65
作問者 : aspi / テスター : NatsubiSogan
お気に入りにしたユーザー ProblemId : 6994 / 自分の提出
問題文最終更新日: 2021-09-11 17:46:03
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original

Problem Statement

There are $N$ points on a two-dimensional plane. Each point is painted either red or blue.

Let the current time be $0$. The points move on the plane. The $i$-th $(1 \leq i \leq N)$ point moves as follows.

  • If $A_i=0$: the color of the $i$-th point is red. It departs from the coordinates $(B_i, 0)$ at time $T_i$ and moves $1$ in the positive direction of the $y$-axis per $1$ unit of time.
  • If $A_i=1$: the color of the $i$-th point is blue. It departs from the coordinates $(0, B_i)$ at time $T_i$ and moves $1$ in the positive direction of the $x$-axis per $1$ unit of time.

Find the number of times a red point and a blue point collide. That is, find the number of pairs of a red point and a blue point such that both are at the same coordinates at some time $t$.

Input

$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}$
  • All input values are integers.

Output

Print the number of times a red point and a blue point collide on one line.

Sample

Sample 1
Input
4
0 1 3
1 2 4
1 5 1
0 5 1
Output
2

A red point and a blue point collide only in the following $2$ cases.

  • At time $5$, points $1,2$ collide at the coordinates $(1,2)$.
  • At time $6$, points $3,4$ collide at the coordinates $(5,5)$.
Sample 2
Input
5
0 1 2
0 1 2
1 1 3
1 1 3
1 1 3
Output
0

It is possible that a red point and a blue point never collide, not even $1$ time. Note that multiple points may depart from the same coordinates.

Sample 3
Input
6
0 1 5
0 5 9
0 8 2
0 1 0
0 100 200
0 200000 200000
Output
0

All points have the same color, so clearly they do not collide even $1$ time.

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