시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB87763373258738.067%

문제

어젯밤 겨울 캠프 장소에서 월드 본원까지 이어지는, 흙으로 된 비밀길 위에 폭우가 내려서 N(1 ≤ N ≤ 10,000)개의 물웅덩이가 생겼다. 월드학원은 물웅덩이를 덮을 수 있는 길이가 L(1 ≤ L ≤ 1,000,000)인 널빤지들을 충분히 가지고 있어서, 이들로 다리를 만들어 물웅덩이들을 모두 덮으려고 한다. 물웅덩이들의 위치와 크기에 대한 정보가 주어질 때, 모든 물웅덩이들을 덮기 위해 필요한 널빤지들의 최소 개수를 구하여라.

입력

첫째 줄에 두 정수 N과 L이 들어온다.

둘째 줄부터 N+1번째 줄까지 총 N개의 줄에 각각의 웅덩이들의 정보가 주어진다. 웅덩이의 정보는 웅덩이의 시작 위치와 끝 위치로 이루어진다. 각 위치는 0 이상 1,000,000,000 이하의 정수이다. 입력으로 주어지는 웅덩이는 겹치지 않는다.

출력

첫째 줄에 모든 물웅덩이들을 덮기 위해 필요한 널빤지들의 최소 개수를 출력한다.

예제 입력 1

3 3
1 6
13 17
8 12

예제 출력 1

5

힌트

아래와 같이 5개의 널빤지가 필요하다.

111222..333444555.... // 길이 3인 널빤지
.MMMMM..MMMM.MMMM.... // 웅덩이
012345678901234567890 // 좌표
W3sicHJvYmxlbV9pZCI6IjE5MTEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ3NTlcdWFlMzggXHViY2Y0XHVjMjE4XHVkNTU4XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1YjRcdWM4MmZcdWJjMjQgXHVhY2E4XHVjNmI4IFx1Y2VhMFx1ZDUwNCBcdWM3YTVcdWMxOGNcdWM1ZDBcdWMxMWMgXHVjNmQ0XHViNGRjIFx1YmNmOFx1YzZkMFx1YWU0Y1x1YzljMCBcdWM3NzRcdWM1YjRcdWM5YzBcdWIyOTQsIFx1ZDc1OVx1YzczY1x1Yjg1YyBcdWI0MWMgXHViZTQ0XHViYzAwXHVhZTM4IFx1YzcwNFx1YzVkMCBcdWQzZWRcdWM2YjBcdWFjMDAgXHViMGI0XHViODI0XHVjMTFjIE4oMSAmbGU7IE4gJmxlOyAxMCwwMDApXHVhYzFjXHVjNzU4IFx1YmIzY1x1YzZjNVx1YjM2OVx1Yzc3NFx1YWMwMCBcdWMwZGRcdWFjYmNcdWIyZTQuIFx1YzZkNFx1YjRkY1x1ZDU1OVx1YzZkMFx1Yzc0MCBcdWJiM2NcdWM2YzVcdWIzNjlcdWM3NzRcdWI5N2MgXHViMzZlXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhZTM4XHVjNzc0XHVhYzAwIEwoMSAmbGU7IEwgJmxlOyAxLDAwMCwwMDApXHVjNzc4IFx1YjExMFx1YmU2NFx1YzljMFx1YjRlNFx1Yzc0NCBcdWNkYTlcdWJkODRcdWQ3ODggXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YzViNFx1YzExYywgXHVjNzc0XHViNGU0XHViODVjIFx1YjJlNFx1YjlhY1x1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWM1YjQgXHViYjNjXHVjNmM1XHViMzY5XHVjNzc0XHViNGU0XHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWIzNmVcdWM3M2NcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWJiM2NcdWM2YzVcdWIzNjlcdWM3NzRcdWI0ZTRcdWM3NTggXHVjNzA0XHVjZTU4XHVjNjQwIFx1ZDA2Y1x1YWUzMFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljOCBcdWI1NGMsIFx1YmFhOFx1YjRlMCBcdWJiM2NcdWM2YzVcdWIzNjlcdWM3NzRcdWI0ZTRcdWM3NDQgXHViMzZlXHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHViMTEwXHViZTY0XHVjOWMwXHViNGU0XHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWFjMWNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHVjNWVjXHViNzdjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWI0NTAgXHVjODE1XHVjMjE4IE5cdWFjZmMgTFx1Yzc3NCBcdWI0ZTRcdWM1YjRcdWM2MjhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgTisxXHViYzg4XHVjOWY4IFx1YzkwNFx1YWU0Y1x1YzljMCBcdWNkMWQgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YzZjNVx1YjM2OVx1Yzc3NFx1YjRlNFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM2YzVcdWIzNjlcdWM3NzRcdWM3NTggXHVjODE1XHViY2Y0XHViMjk0IFx1YzZjNVx1YjM2OVx1Yzc3NFx1Yzc1OCBcdWMyZGNcdWM3OTEgXHVjNzA0XHVjZTU4XHVjNjQwIFx1YjA1ZCBcdWM3MDRcdWNlNThcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVjNzA0XHVjZTU4XHViMjk0IDAgXHVjNzc0XHVjMGMxIDEsMDAwLDAwMCwwMDAgXHVjNzc0XHVkNTU4XHVjNzU4IFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC4gXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWM2YzVcdWIzNjlcdWM3NzRcdWIyOTQgXHVhY2I5XHVjZTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmFhOFx1YjRlMCBcdWJiM2NcdWM2YzVcdWIzNjlcdWM3NzRcdWI0ZTRcdWM3NDQgXHViMzZlXHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHViMTEwXHViZTY0XHVjOWMwXHViNGU0XHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzc0IDVcdWFjMWNcdWM3NTggXHViMTEwXHViZTY0XHVjOWMwXHVhYzAwIFx1ZDU0NFx1YzY5NFx1ZDU1OFx1YjJlNC48XC9wPlxyXG5cclxuPHByZT5cclxuMTExMjIyLi4zMzM0NDQ1NTUuLi4uIFwvXC8gXHVhZTM4XHVjNzc0IDNcdWM3NzggXHViMTEwXHViZTY0XHVjOWMwXHJcbi5NTU1NTS4uTU1NTS5NTU1NLi4uLiBcL1wvIFx1YzZjNVx1YjM2OVx1Yzc3NFxyXG4wMTIzNDU2Nzg5MDEyMzQ1Njc4OTAgXC9cLyBcdWM4OGNcdWQ0NWM8XC9wcmU+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTkxMSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik11ZGR5IHJvYWRzIiwiZGVzY3JpcHRpb24iOiI8cD5GYXJtZXIgSm9obiBoYXMgYSBwcm9ibGVtOiB0aGUgZGlydCByb2FkIGZyb20gaGlzIGZhcm0gdG8gdG93biBoYXMgc3VmZmVyZWQgaW4gdGhlIHJlY2VudCByYWluc3Rvcm1zIGFuZCBub3cgY29udGFpbnMgKDEgJmxlOyBOICZsZTsgMTAsMDAwKSBtdWQgcG9vbHMuPFwvcD5cclxuXHJcbjxwPkZhcm1lciBKb2huIGhhcyBhIGNvbGxlY3Rpb24gb2Ygd29vZGVuIHBsYW5rcyBvZiBsZW5ndGggKDEgJmxlOyBMICZsZTsgMSwwMDAsMDAwKSB0aGF0IGhlIGNhbiB1c2UgdG8gYnJpZGdlIHRoZXNlIG11ZCBwb29scy4gSGUgY2FuIG92ZXJsYXAgcGxhbmtzIGFuZCB0aGUgZW5kcyBkbyBub3QgbmVlZCB0byBiZSBhbmNob3JlZCBvbiB0aGUgZ3JvdW5kLiBIb3dldmVyLCBoZSBtdXN0IGNvdmVyIGVhY2ggcG9vbCBjb21wbGV0ZWx5LjxcL3A+XHJcblxyXG48cD5HaXZlbiB0aGUgbXVkIHBvb2xzLCBoZWxwIEZKIGZpZ3VyZSBvdXQgdGhlIG1pbmltdW0gbnVtYmVyIG9mIHBsYW5rcyBoZSBuZWVkcyBpbiBvcmRlciB0byBjb21wbGV0ZWx5IGNvdmVyIGFsbCB0aGUgbXVkIHBvb2xzLjxcL3A+XHJcbiIsImlucHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IFR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnM6IE4gYW5kIEw8XC9saT5cclxuXHQ8bGk+TGluZXMgMi4uTisxOiBMaW5lIGkrMSBjb250YWlucyB0d28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzOiBzPHN1Yj5pPFwvc3ViPiBhbmQgZTxzdWI+aTxcL3N1Yj4gKDAgJmxlOyBzPHN1Yj5pPFwvc3ViPiAmbHQ7IGU8c3ViPmk8XC9zdWI+ICZsZTsgMSwwMDAsMDAwLDAwMCkgdGhhdCBzcGVjaWZ5IHRoZSBzdGFydCBhbmQgZW5kIHBvaW50cyBvZiBhIG11ZCBwb29sIGFsb25nIHRoZSByb2FkLiBUaGUgbXVkIHBvb2xzIHdpbGwgbm90IG92ZXJsYXAuIFRoZXNlIG51bWJlcnMgc3BlY2lmeSBwb2ludHMsIHNvIGEgbXVkIHBvb2wgZnJvbSAzNSB0byAzOSBjYW4gYmUgY292ZXJlZCBieSBhIHNpbmdsZSBib2FyZCBvZiBsZW5ndGggNC4gTXVkIHBvb2xzIGF0ICgzLDYpIGFuZCAoNiw5KSBhcmUgbm90IGNvbnNpZGVyZWQgdG8gb3ZlcmxhcC48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBUaGUgbWltaW51bSBudW1iZXIgb2YgcGxhbmtzIEZKIG5lZWRzIHRvIHVzZS48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiI8cD5GSiBuZWVkcyB0byB1c2UgcGxhbmtzIG9mIGxlbmd0aCAzIHRvIGNvdmVyIDMgbXVkIHBvb2xzLiBUaGUgbXVkIHBvb2xzIGNvdmVyIHJlZ2lvbnMgMSB0byA2LCA4IHRvIDEyLCBhbmQgMTMgdG8gMTcuPFwvcD5cclxuXHJcbjxwPkZKIGNhbiBjb3ZlciB0aGUgbXVkIHBvb2xzIHdpdGggZml2ZSBwbGFua3Mgb2YgbGVuZ3RoIDMgaW4gdGhlIGZvbGxvd2luZyB3YXk6PFwvcD5cclxuXHJcbjxwcmU+XHJcbiAgICAgICAgICAgICAgICAgICAxMTEyMjIuLjMzMzQ0NDU1NS4uLi5cclxuICAgICAgICAgICAgICAgICAgIC5NTU1NTS4uTU1NTS5NTU1NLi4uLlxyXG4gICAgICAgICAgICAgICAgICAgMDEyMzQ1Njc4OTAxMjM0NTY3ODkwPFwvcHJlPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Olympiad > USA Computing Olympiad > 2004-2005 Season > USACO US Open 2005 Contest > Silver 4번

  • 잘못된 번역을 찾은 사람: skeep194