시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 48 30 28 68.293%

문제

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

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

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

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

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

입력

각 테스트 케이스의 첫째 줄에는 전화 통화의 수 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초는 구간 안에 있어야 한다.

예제 입력 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

예제 출력 1

3
2
1
0
W3sicHJvYmxlbV9pZCI6IjM4NjMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1ODlcdWJjZjVcdWQ1NWMgXHVjODA0XHVkNjU0IFx1ZDFiNVx1ZDY1NCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjYzNkXHVjNjAxIFx1YzY1NVx1YWQ2ZFx1YzVkMFx1YjI5NCBcdWM4MDRcdWQ2NTRcdWM2NDAgXHVhZDAwXHViODI4XHViNDFjIFx1YzJlMFx1YWUzMFx1ZDU1YyBcdWJjOTVcdWM3NzQgXHVkNTU4XHViMDk4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPGJsb2NrcXVvdGU+XHVkMWI1XHVkNjU0IFx1YzkxMVx1YzVkMCBcdWMwYzFcdWIzMDBcdWJjMjlcdWM1ZDBcdWFjOGMgXHVkNjU0XHViOTdjIFx1YjBiNFx1YmE3NCBcdWFjMTBcdWM2MjVcdWM1ZDAgXHVhYzA0XHViMmU0LjxcL2Jsb2NrcXVvdGU+XHJcblxyXG48cD5cdWFjYmRcdWNjMzBcdWM3NDAgXHVkNjU0XHViOTdjIFx1YjBiNFx1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NDQgXHViMmU4XHVjMThkXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWJhYThcdWI0ZTAgXHVjODA0XHVkNjU0IFx1ZDFiNVx1ZDY1NFx1Yjk3YyBcdWIzYzRcdWNjYWRcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjYmRcdWNjMzBcdWM3NDAgXHVjOWMxXHVjNmQwXHVjNzQ0IFx1YzgwMVx1YzgwOFx1ZDc4OCBcdWJmNTFcdWM1NDRcdWMxMWMgXHVkMmI5XHVjODE1IFx1YzJkY1x1YWMwNCBcdWIzZDlcdWM1NDggXHViYWE4XHViNGUwIFx1YzgwNFx1ZDY1NFx1Yjk3YyBcdWIzYzRcdWNjYWRcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWFjMDEgXHVjOWMxXHVjNmQwXHVjNzQwIFx1YjNjNFx1Y2NhZFx1Yzc0NCBcdWQ1NThcdWFlMzAgXHVjODA0XHVjNWQwIFx1YjllNFx1YzZiMCBcdWM2MjRcdWI3OWMgXHVjMmRjXHVhYzA0XHViM2Q5XHVjNTQ4IFx1ZDczNFx1YzJkZFx1Yzc0NCBcdWNkZThcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjYmRcdWNjMzBcdWM3NDAgXHVjZDFkIFx1YmE4NyBcdWJhODVcdWM3NTggXHVjOWMxXHVjNmQwXHVjNzQ0IFx1YWNlMFx1YzZhOVx1ZDU3NFx1YzU3YyBcdWQ1NThcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM2MmNcdWJjMTRcdWI5NzRcdWFjOGMgXHVjNzkxXHVjMTMxXHVkNTU4XHVjOWMwIFx1YmFiYlx1ZDU1YyBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVkNjU0XHViOTdjIFx1YjBiOCBcdWMwYWNcdWI3OGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YWMxMFx1YzYyNVx1YzVkMCBcdWFjMDBcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM4MDRcdWQ2NTQgXHVkMWI1XHVkNjU0XHVjNzU4IFx1YzIxOCBOICgxICZsZTsgTiAmbHQ7IDEwLDAwMClcdWFjZmMgXHVhZDZjXHVhYzA0XHVjNzU4IFx1YzIxOCBNICgxICZsZTsgTSAmbHQ7IDEwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjODA0XHVkNjU0IFx1ZDFiNVx1ZDY1NFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBcdWNkMWQgXHViMTI0IFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMThcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjYzI4XHViODQwXHViMzAwXHViODVjIFNvdXJjZSwgRGVzdGluYXRpb24sIFN0YXJ0LCBEdXJhdGlvbiBcdWM3NzRcdWJhNzAsIFNvdXJjZVx1YzY0MCBEZXN0aW5hdGlvblx1YjI5NCAwXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIDEwLDAwMCwwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuIER1cmF0aW9uXHViMjk0IFx1ZDFiNVx1ZDY1NCBcdWMyZGNcdWFjMDRcdWM3NDQgXHVjZDA4XHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiOCBcdWFjODNcdWM3NzRcdWFjZTAsIFN0YXJ0XHViMjk0IFx1YmMxY1x1YzJlMCBcdWMyZGNcdWFjMDRcdWM3NzRcdWIyZTQuICgxICZsZTsgRHVyYXRpb24gJmxlOyAxMCwwMDAsIFN0YXJ0ICZnZTsgMCkgXHViYWE4XHViNGUwIFN0YXJ0XHVjNjQwIER1cmF0aW9uIFx1ZDU2OVx1Yzc0MCBcdWJkODBcdWQ2MzhcdWM3ODhcdWIyOTQgMzJcdWJlNDRcdWQyYjggXHViYzk0XHVjNzA0XHVjNTQ4XHVjNWQwIFx1YjRlNFx1YzViNFx1YWMwNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE1cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWNiZFx1Y2MzMFx1Yzc3NCBcdWIzYzRcdWNjYWRcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTU4XHViMjk0IFx1YWQ2Y1x1YWMwNFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBcdWI0NTAgXHVjODE1XHVjMjE4IFN0YXJ0XHVjNjQwIER1cmF0aW9uXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwXHVjNzc0IFx1YjQ1MCBcdWFjMWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWFkNmNcdWFjMDRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWFkNmNcdWFjMDRcdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDE4XHViMjk0IFx1YzgwNFx1ZDY1NCBcdWQxYjVcdWQ2NTRcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjODA0XHVkNjU0IFx1ZDFiNVx1ZDY1NFx1YWMwMCBcdWFkNmNcdWFjMDRcdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDE4XHViODI0XHViYTc0LCBcdWM4MDFcdWM1YjRcdWIzYzQgMVx1Y2QwOFx1YjI5NCBcdWFkNmNcdWFjMDQgXHVjNTQ4XHVjNWQwIFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzg2MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkhhcHB5IFRlbGVwaG9uZXMiLCJkZXNjcmlwdGlvbiI6IjxwPkluIHRoZSBsYW5kIG9mIEVkZW4sIGFsbCBwaG9uZSBjb252ZXJzYXRpb25zIGFyZSBoYXBweSBvbmVzLiBQZW9wbGUgY29tcGxhaW5pbmcgb24gdGhlIHBob25lIGFyZSBpbW1lZGlhdGVseSBwdXQgaW4gamFpbC4gVG8gZW5mb3JjZSB0aGlzIGxhdywgdGhlIHBvbGljZSB0YXBzIGFsbCBwaG9uZSBjb252ZXJzYXRpb25zLjxcL3A+XHJcblxyXG48cD5UaGUgcG9saWNlIHdhbnRzIHRvIGhpcmUgdGhlIGFwcHJvcHJpYXRlIG51bWJlciBvZiBvcGVyYXRvcnMgdG8gbGlzdGVuIHRvIGFsbCBjb252ZXJzYXRpb25zIGluIGEgZ2l2ZW4gcGVyaW9kIG9mIHRpbWUuIFVuZm9ydHVuYXRlbHksIGVhY2ggb2YgdGhlaXIgb3BlcmF0b3JzIGNhbiBsaXN0ZW4gdG8gb25lIGNvbnZlcnNhdGlvbiBvbmx5IGJlZm9yZSBuZWVkaW5nIGEgcmVhbGx5IGxvbmcgYnJlYWsgdG8gcmVzdCBmcm9tIHRoZSBlZmZvcnQuPFwvcD5cclxuXHJcbjxwPkFzIGEgY29udHJhY3RvciBvZiB0aGUgcG9saWNlIGRlcGFydG1lbnQsIHlvdSBoYXZlIGJlZW4gYXNrZWQgdG8gcHJvdmlkZSBhIHByb2dyYW0gY2FwYWJsZSBvZiBkZXRlcm1pbmluZyB0aGUgcmVxdWlyZWQgbnVtYmVyIG9mIG9wZXJhdG9ycy4gSWYgdGhlIHByb2dyYW0gZG9lcyBub3Qgd29yayBjb3JyZWN0bHksIHlvdSB3aWxsIGJlIHB1dCBpbiBqYWlsIGFzIHdlbGwsIGFsb25nIHdpdGggYWxsIHRoZSB1bmhhcHB5IGNvbXBsYWluZXJzLiBEbyB5b3UgcmVhbGx5IHdhbnQgdG8gZW5kIHVwIHRoZXJlPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+RWFjaCB0ZXN0IGNhc2Ugc3RhcnRzIHdpdGggdHdvIGludGVnZXJzIGRlbm90aW5nIHRoZSBudW1iZXIgb2YgcGhvbmUgY2FsbHMgTiAoMSAmbGU7IE4gJmx0OyAxMCAwMDApIGFuZCB0aGUgbnVtYmVyIG9mIGludGVydmFscyBNICgxICZsZTsgTSAmbHQ7IDEwMCkuIFRoaXMgaXMgZm9sbG93ZWQgYnkgTiBsaW5lcyBkZXNjcmliaW5nIHRoZSB0ZWxlcGhvbmUgY2FsbHMsIGVhY2ggb25lIGNvbnNpc3Rpbmcgb2YgZm91ciBpbnRlZ2VycyBTb3VyY2UsIERlc3RpbmF0aW9uLCBTdGFydCBhbmQgRHVyYXRpb24uIFNvdXJjZSBhbmQgRGVzdGluYXRpb24gaWRlbnRpZnkgdGhlIHBhaXIgb2YgdGVsZXBob25lIG51bWJlcnMgZXN0YWJsaXNoaW5nIHRoZSBjb25uZWN0aW9uICgwICZsZTsgU291cmNlLCBEZXN0aW5hdGlvbiAmbGU7IDEwIDAwMCAwMDApLiBTdGFydCBhbmQgRHVyYXRpb24gYXJlIHRoZSBzdGFydCB0aW1lIGFuZCBkdXJhdGlvbiBvZiB0aGUgY2FsbCBpbiBzZWNvbmRzICgxICZsZTsgRHVyYXRpb24gJmxlOyAxMCAwMDAgYW5kIFN0YXJ0ICZnZTsgMCkuIFlvdSBjYW4gc2FmZWx5IGFzc3VtZSB0aGF0IHRoZSBzdW0gb2YgU3RhcnQgYW5kIER1cmF0aW9uIGZpdHMgaW50byBhIDMyLWJpdCBzaWduZWQgaW50ZWdlci48XC9wPlxyXG5cclxuPHA+QWZ0ZXJ3YXJkcyBmb2xsb3cgTSBsaW5lcyBjb250YWluaW5nIHRoZSB0aW1lIGludGVydmFscyB0aGUgcG9saWNlIGFyZSBpbnRlcmVzdGVkIGluLCBlYWNoIG9uIGRlc2NyaWJlZCBieSB0d28gaW50ZWdlcnMgU3RhcnQgYW5kIER1cmF0aW9uLCBpbiB0aGUgc2FtZSBmb3JtYXQgYW5kIHdpdGggdGhlIHNhbWUgbWVhbmluZyBhbmQgY29uc3RyYWludHMgYXMgdGhvc2UgaW4gdGhlIHRlbGVwaG9uZSBjYWxscy4gVGhlIGxhc3QgdGVzdCBjYXNlIGlzIHJlcHJlc2VudGVkIGJ5IE4gPSBNID0gMCBhbmQgbXVzdCBub3QgYmUgcHJvY2Vzc2VkLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIG9mIHRoZSBNIGludGVydmFscyBvZiBlYWNoIHRlc3QgY2FzZSwgcHJpbnQgdGhlIG51bWJlciBvZiBjYWxscyB0aGF0IGFyZSBhY3RpdmUgZHVyaW5nIGF0IGxlYXN0IG9uZSBzZWNvbmQgb2YgdGhlIGludGVydmFsLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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

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