A16146 | Panda Meetups

The red pandas are in town to meet their relatives, the blue pandas! The town is modeled by a number line.

The pandas have already planned their meetup, but the schedule keeps changing. You are given $q$ updates of the form x t c.

- If $c < 0$ , it means $|c|$ more red pandas enter the number line at position $x$ and time $t$ . Then, each unit of time, they can each independently move one unit in either direction across the number line, or not move at all.
- If $c > 0$ , it means that $c$ more blue pandas check position $x$ for red pandas at time $t$ . If a blue panda does not meet a red panda at that specific location and time, they dejectedly leave the number line right away. If there is a red panda at a position at the same time a blue panda checks it, they form a friendship and leave the number line. Each red panda can form a friendship with at most one blue panda and vice versa.

The updates will be given in order of non-decreasing $x$ values. After each update, please print the maximum number of friendships if the red pandas move in an optimal order based on all the updates given in the input above (and including) this update.

The order in which a red panda moves can change between updates.

The first line contains $q$ ( $1 \leq q \leq 2 \cdot 10^5$ ) – the number of updates.

The $i$ -th line of the next $q$ lines consists of $3$ integers $x_i$ , $t_i$ and $c_i$ ( $0 \leq x_i \leq 10^9$ , $0 \leq t_i \leq 10^9$ , $0 < |c_i| \leq 1000$ ) – the description of the $i$ -th update.

It is guaranteed that the $x_i$ will be given in non-decreasing order.

After each update, print the maximum number of friendships that can be formed.