Boxlings

Doctor Y, always eager to further his research in the field of boxology, is observing a family of boxen in their natural habitat - a barrel of wine. He has noticed that in addition to the N (1 ≤ N ≤ 200,000) rectangular, two-dimensional boxen, there are M (1 ≤ M ≤ 200,000) almost imperceptible points floating on the surface of the wine. He reasons that these must be baby boxen - also known as boxlings.

Curious as to the customs of box families, Doctor Y wishes to count how many boxlings are floating on top of boxne. From his top-down view of the barrel, he has divided the surface of the wine into a two-dimensional Catersian plane, and noted the positions of all the boxen and boxlings. Each box occupies a rectangular region parallel to the axes of the plane, with its lower-left corner at (x₁, y₁) and its upper-right corner at (x₂, y₂), such that (-10⁸ ≤ x₁ < x₂ ≤ 10⁸) and (-10⁸ ≤ y₁ < y₂ ≤ 10⁸). Doctor Y has observed that boxen sometimes overlap one another. Each boxling is so small that it occupies only a single point on the plane, with x-coordinate a and y-coordinate b, such that (-10⁸ ≤ a, b ≤ 10⁸).

Having recorded the locations of all the life forms on the surface of the wine, Doctor Y is interested in counting exactly how many boxlings are floating on top of at least one box. Note that if a boxling is on the very edge or corner of a box, it counts as being on top. Also note that two boxlings can occupy the exact same locations, and that they should be counted separately.

With so many boxen and boxlings living in this wine barrel, Doctor Y doesn't feel like sitting there and counting them all by hand, crazy though he is. As such, he wants you to write a program to, given the locations of all the boxen and boxlings, count the number of boxlings that are floating on top of at least one box. Don't worry; your hard work will surely lead to exciting discoveries in the field of boxology.

Input

Output

A single integer - the number of boxlings that are on top of at least one box.

Sample Input

5 10
-1 -1 2 5
4 -3 5 3
1 2 4 4
5 -6 8 -4
1 -2 8 0
1 4
5 4
2 2
3 1
6 -5
5 -1
3 -3
-1 -2
-1 -1
2 -1

Sample Output

6

Explanation

Below is a top-down view of the surface of the wine:

The coloured-in squares are the boxen, the red dots are boxlings that are on top of at least one box, and the blue dots are the other boxlings. Counting the red dots, it can be seen that there are six of them.

All Submissions
Best Solutions

Point Value: 20 (partial)
Time Limit: 3.00s
Memory Limit: 256M
Added: May 30, 2009
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

For each box, (x1,y1) and (x2,y2) are opposite corners (x2>x1 and y2>y1 don't necessarily hold).

Additionally, a box may have zero area, in which case it's treated as a line (or a point) and may still have boxlings on top of it.

Treating boxen which have x1>x2 and y1>y2 as valid boxes gives me WA?

This problem can be solved with a data structure known as a 2D range tree. It can be researched on the internet and implemented without too much trouble.

So 2D range tree is less nasty than 2D BIT? Or do we not agree on what a range tree [i]is[/i]?

It's not too bad...but I don't know, I've never coded a 2D BIT. You could try this problem and see for yourself what I mean by a range tree.

If it's a 2DBIT I'm not coding it...

It's not quite that nasty.