No.1679 Mass Game
タグ : / 解いたユーザー数 65
作問者 :
aspi
/ テスター :
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もしくは右上の雲マークをクリックしてアカウントを作成してください。