BOXLINGS - Boxlings

no tags 

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 \leq N \leq 200,000$) rectangular, two-dimensional boxen, there are $M$ ($1 \leq M \leq 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 boxen. From his top-down view of the barrel, he has divided the surface of the wine into a two-dimensional Cartesian 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 two of its opposite corners at coordinates ($x_1$, $y_1$) and ($x_2$, $y_2$). Doctor Y has observed that boxen sometimes overlap with one another. On the other hand, each boxling is so small that it occupies only a single point on the plane, with x-coordinate $a$ and y-coordinate $b$. All coordinates have absolute values no larger than $10^9$.

Having recorded the locations of all of 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, in which case they should still be counted separately. It's also possible for a box to have zero area, in which case it's treated as a line (or point) and can still have boxlings on top of it.

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. 


Line $1$: 2 integers, $N$ and $M$

Next $N$ lines: 4 integers, $x_1$, $y_1$, $x_2$, and $y_2$, the coordinates of each box

Next $M$ lines: 2 integers, $a$ and $b$, the coordinates of each boxling


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


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
Explanation of Sample:

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

The coloured-in rectangles 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.


hide comments
vilay: 2013-06-24 17:44:50

please give me any tricky case for which my program give wrong ans?
it run's till status of running(15..)
not able to get what's wrong with my code.
submission id:9542945

RE: I don't know why it shows up as WA, it should be TLE - your solution is far too slow.

Last edit: 2013-09-09 22:58:23
Hasan Jaddouh: 2013-05-17 00:15:08

"All coordinates have absolute values no larger than 10^8"

I think this constrain is not satisfied.
please check

RE: Indeed, some values have magnitude up to 10^9 instead... the problem's been updated.

Last edit: 2013-05-17 00:15:46
Edelweiss: 2013-05-17 00:15:08

I've checked my code again and again but still cannot find any problem. I'm afraid there existed some subtle error in my code that would cause big trouble in my future coding.

Could you have a look at my code?
This is my e-mail:
If you would like, please contact me :)

RE: Have you tried making some random cases, maybe generated, and checking your answers using brute force?

EDIT: Yeah, always the same result...Maybe my code got stuck on some tricky case. I want to ask for the input & output data of just one case on which I got WA. Could you?

RE: Ah, I'm sorry to have wasted your time, but it turned out that the data was flawed! It didn't satisfy the conditions that x2>x1 and y2>y1. The problem statement's been updated accordingly.

EDIT: Thanks :)

Last edit: 2013-05-09 10:59:20
Edelweiss: 2013-05-17 00:15:08

Y-axis coordinates discretization + segment tree + X-axis line scan?
I'm not sure if I've made some stupid mistake or there's something wrong with test data #15.
Could you please help me check it?

RE: I'm sure you're on the right track, but your outputs are incorrect for about half of the cases.

EDIT: Oops...thanks!

Last edit: 2013-05-09 04:28:43

Added by:SourSpinach
Time limit:4s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem