All Tracks Algorithms Dynamic Programming Introduction to Dynamic Programming 1 Problem

Family competition

Algorithms, Dynamic Programming, Fenwick Tree, Medium, Segment Trees, Sorting


Two families The Bakers and The Murtaughs are rival families and they are competing in a final round of the competition, which is to decide who of these two families are going to be the winners of the competition. The purpose of the competition being union and friendship of the families, the last competition requires both families to collaborate on getting the best result they can achieve.

They are playing volleyball like game. We can describe volleyball field as an $$x$$-axis, the net is located at point 0. Each of the Bakers is located in negative part of $$x$$-axis, so that $$x_i < 0$$, it's $$-x_i$$ meters away from the net. And each of the Murtaughs is located in positive part of $$x$$-axis, so that $$x_i>0$$, it's $$x_i$$ meters away from the net. For each family member her age $$a_i$$ seconds since birth is known.

The goal of the game is to choose who should start the game and then make maximum possible number of ball throws.

The game proceeds as follows. At first one of the family members is given a ball. Any family member of any of two families can be given a ball. On each throw, player who has a ball throws it to one of the players of the other family, and so on.

A player can throw a ball only to the player of the opposite team, who is strictly older than her. Family members are not so strong, so each of them can throw a ball $$h$$ meters from her location. Formally, player $$i$$ can throw ball to player $$j$$, if $$\operatorname{sign}{(x_i)} \ne \operatorname{sign}{(x_j)}$$, $$a_i < a_j$$ and $$|x_i - x_j| \le h$$, where $$\operatorname{sign}$$ is a Sign function.

Find the maximum number of throws families can achieve.

Input format

First line of input contains two integers $$n$$ and $$h$$ — the total number of members in both families and the maximum distance they can make single throw on.

Each of the next $$n$$ lines consists of two integers $$a_i$$ and $$x_i$$ — age and location of the $$i$$-th family member.


$$2 \le n \le 2 \cdot 10^5$$

$$2 \le h \le 2 \cdot 10^5$$

$$1 \le a_i \le 10^5$$

All coordinates don't exceed $$10^5$$ by their absolute value and $$x_i \ne 0$$.

Output format

Output single integer: the maximum number of ball throws families can achieve.

6 4
2 -2
3 1
5 -4
12 1
6 -1
3 3

Family member 1 located in $$x=-2$$ throws ball to family member 2 located in $$x=1$$. Family member 2 is older than family member 1 and their positions differ by 3. Then Family member 2 throws ball to family member 5 located in $$x=-1$$, and finally, family member 5 throws ball to family member 4.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic


Initializing Code Editor...
Your Rating:


This Problem was Asked in


Challenge Name

February Easy '17

View All Notifications