TTREAT - Happy Telephones

no tags 

In the land of Eden, all phone conversations are happy ones. People com-plaining on the phone are immediately put in jail. To enforce this law, the police taps all phone conversations. The police wants to hire the appropriate number of operators to listen to all conversations in a given period of time. Unfortunately, each of their operators can listen to one conversation only before needing a really long break to rest from the effort. As a contractor of the police department, you have been asked to provide a program capable of determining the required number of operators. If the program does not work correctly, you will be put in jail as well, along with all the unhappy complainers. Do you really want to end up there? Telephone operators. Photo: Seattle Municipal Archives.

Input

Each test case starts with two integers denoting the number of phone calls N (1 <= N <= 10000) and the number of intervals M (1 <= M <= 100). This is followed by N lines describing the telephone calls, each one consisting of four integers Source, Destination, Start and Duration. Source and Destination identify the pair of telephone numbers establishing the connection (0 <= Source; Destination <= 10000000). Start and Duration are the start time and duration of the call in seconds (1 <= Duration <= 10000 and Start >= 0). You can safely assume that the sum of Start and Duration fits into a 32-bit signed integer. Afterwards follow M lines containing the time intervals the police are interested in, each on described by two integers Start and Duration, in the same format and with the same meaning and constraints as those in the telephone calls. The last test case is represented by N = M = 0 and must not be processed.

Output

For each of the M intervals of each test case, print the number of calls that are active during at least one second of the interval.

Sample

Input
3 2
3 4 2 5
1 2 0 10
6 5 5 8
0 6
8 2
1 2
8 9 0 10
9 1
10 1
0 0

Output
3
2
1
0

hide comments
Mitch Schwartz: 2011-11-25 07:38:16

This problem was republished to SPOJ as HAPPYTL along with the other SWERC 2009 problems. This one was hidden or moved to tutorial to keep the problem set intact.

:D: 2011-02-02 14:55:13

Be careful with buffering input. I had some strange issues with a fast input method I used successfully for dozens of other problems.

David García Soriano: 2010-11-18 11:00:22

As Abel said, test data is not weak. This is just supposed to be a trivial problem, as the constraints shoud make clear.

On the other hand it baffles me how this problem was uploaded to spoj, instead of the other (very interesting) problems in the contest.

Abel Molina: 2010-11-14 07:51:39

One of the problemsetters of SWERC 09 here: This was supposed to be the easy problem in the contest that everyone (or at least everyone) should solve :), so we did not force solutions to be very efficient.

There are more challenging problems in the set, of course ;) (right now only at the ACM ICPC Live Archive I believe)

:(){ :|: & };:: 2010-08-18 15:48:46


I solved it using both O(log(N) * (M + N))and the trivial O(N*M),giving 0.05 in the former and 0.09 in the later so,the difference is only about 0.04 sec (with or without FAST I/O).

Last edit: 2010-08-18 15:49:45
Vimal poonia: 2010-08-15 13:05:30

@ Author
please check the termination condition in input :)

Last edit: 2010-08-15 13:08:42
madhav: 2010-08-15 11:52:12

@Anil we can solve it in O(M*logn) :D

Anil Kishore: 2010-08-15 11:39:31

Not weak test cases, constraints itself are weak, as N*M is at max 10^6.
Would be a nice problem if 1 <= N,M <= 10^5

Oleg: 2010-08-15 11:11:29

O(NM) passed with 0.00, maybe weak test cases ?

Reply: These are the official test cases..

Last edit: 2010-08-15 13:25:21

Added by:Gareev
Date:2010-08-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 VB.NET
Resource:SWERC 2009