시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 30 19 18 75.000%

문제

창영 왕국에는 전화와 관련된 신기한 법이 하나 있다.

통화 중에 상대방에게 화를 내면 감옥에 간다.

경찰은 화를 내는 사람을 단속하기 위해서 모든 전화 통화를 도청하려고 한다.

경찰은 직원을 적절히 뽑아서 특정 시간 동안 모든 전화를 도청하려고 한다. 각 직원은 도청을 하기 전에 매우 오랜 시간동안 휴식을 취해야 한다.

경찰은 총 몇 명의 직원을 고용해야 하는지 구하는 프로그램을 작성하시오. 프로그램을 올바르게 작성하지 못한 경우에는 화를 낸 사람과 같이 감옥에 가야 한다.

입력

각 테스트 케이스의 첫째 줄에는 전화 통화의 수 N (1 ≤ N < 10,000)과 구간의 수 M (1 ≤ M < 100)이 주어진다. 다음 N개 줄에는 전화 통화의 정보가 주어지며, 총 네 개의 정수로 이루어져 있다. 차례대로 Source, Destination, Start, Duration 이며, Source와 Destination는 0보다 크거나 같고, 10,000,000보다 작거나 같은 정수이다. Duration는 통화 시간을 초로 나타낸 것이고, Start는 발신 시간이다. (1 ≤ Duration ≤ 10,000, Start ≥ 0) 모든 Start와 Duration 합은 부호있는 32비트 범위안에 들어간다.

다음 M개 줄에는 경찰이 도청하려고 하는 구간의 정보가 주어지며, 두 정수 Start와 Duration으로 이루어져 있다. 테스트 케이스의 마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스마다 각각의 구간에 대해서, 구간에 포함되는 전화 통화의 수를 출력한다. 전화 통화가 구간에 포함되려면, 적어도 1초는 구간 안에 있어야 한다.

예제 입력

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

예제 출력

3
2
1
0

힌트

출처

ACM-ICPC > Regionals > Europe > Southwestern European Regional Contest > SWERC 2009 I번

  • 문제의 오타를 찾은 사람: Acka
  • 문제를 번역한 사람: baekjoon