์‹œ๊ฐ„ ์ œํ•œ ๋ฉ”๋ชจ๋ฆฌ ์ œํ•œ ์ œ์ถœ ์ •๋‹ต ๋งž์€ ์‚ฌ๋žŒ ์ •๋‹ต ๋น„์œจ
1 ์ดˆ 1024 MB 26 16 13 65.000%

๋ฌธ์ œ

๐ŸŽต๋‹ˆ๊ฐ€ ์‹ซ์–ด ์‹ซ์–ด ๋„ˆ๋ฌด ์‹ซ์–ด ์‹ซ์–ด ์˜ค์ง€๋งˆ ๋‚ด๊ฒŒ ์ฐ์ฉ๋Œ€์ง€๋งˆ๐ŸŽต - ์œ ์ž, ๋ชจ๊ธฐ์†ก ไธญ

์–ด๋Š ๋‚  ์†Œ๋ฏผ์ด๋Š” ์ž์‹ ์˜ ๋ฐฉ ์ฐฝ๋ฌธ ๋ฐฉ์ถฉ๋ง์— ๊ตฌ๋ฉ์ด ๋šซ๋ ค์žˆ๋‹ค๋Š” ์‚ฌ์‹ค์„ ์•Œ๊ฒŒ ๋˜์—ˆ๋‹ค. ๋ชจ๊ธฐ๊ฐ€ ๋ฐฉ์— ๋“ค์–ด์˜ค๋Š” ๊ฒŒ ์‹ซ์€ ์†Œ๋ฏผ์ด๋Š” ๋ฐฉ์ถฉ๋ง์„ ๋ณด์ˆ˜ํ•˜๋ ค๊ณ  ํ•œ๋‹ค. ํ•˜์ง€๋งŒ ์†Œ๋ฏผ์ด๋Š” ํ•˜๋‚˜์˜ ๋ฐฉ์ถฉ๋ง ๋ณด์ˆ˜ ์Šคํ‹ฐ์ปค๋งŒ ๊ฐ–๊ณ  ์žˆ๋‹ค. ๋ฐฉ์ถฉ๋ง ๋ณด์ˆ˜ ์Šคํ‹ฐ์ปค๋Š” ๊ฐ€๋กœ์™€ ์„ธ๋กœ์˜ ๊ธธ์ด๊ฐ€ ๊ฐ™์€ ์ •์‚ฌ๊ฐํ˜•์ด๋‹ค. ์†Œ๋ฏผ์ด๋Š” ์ด ํ•œ ์žฅ์˜ ์Šคํ‹ฐ์ปค๋กœ ์ตœ๋Œ€ํ•œ ๋งŽ์€ ๊ตฌ๋ฉ์„ ๋นˆํ‹ˆ์—†์ด ๊ฐ€๋ฆฌ๊ณ  ์‹ถ์–ด ํ•œ๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด ๊ตต์€ ํ…Œ๋‘๋ฆฌ์˜ ์ง์‚ฌ๊ฐํ˜•๋“ค์— ๊ตฌ๋ฉ์ด ๋šซ๋ ค์žˆ๋‹ค๊ณ  ํ•˜์ž. ๋นจ๊ฐ„์ƒ‰ ์ •์‚ฌ๊ฐํ˜• ํฌ๊ธฐ์˜ ๋ฐฉ์ถฉ๋ง ๋ณด์ˆ˜ ์Šคํ‹ฐ์ปค๊ฐ€ ์žˆ์„ ๋•Œ ๋นˆํ‹ˆ์—†์ด ์ตœ๋Œ€๋กœ ๋ง‰์„ ์ˆ˜ ์žˆ๋Š” ๊ตฌ๋ฉ์€ 4๊ฐœ๊ฐ€ ๋œ๋‹ค. ๋นˆํ‹ˆ์—†์ด ์ตœ๋Œ€ํ•œ ๋งŽ์€ ๊ตฌ๋ฉ์„ ๋ง‰์„ ์ˆ˜ ์žˆ๋Š” ๋ฐฉ์ถฉ๋ง ๋ณด์ˆ˜ ์Šคํ‹ฐ์ปค์˜ ์œ„์น˜๋Š” ์œ ์ผํ•˜์ง€ ์•Š์„ ์ˆ˜ ์žˆ๋‹ค.

๋ฐฉ์ถฉ๋ง ๋ณด์ˆ˜ ์Šคํ‹ฐ์ปค๋ฅผ ์ž˜ ๋ถ™์˜€์„ ๋•Œ ๋นˆํ‹ˆ์—†์ด ์ตœ๋Œ€๋กœ ๋ง‰์„ ์ˆ˜ ์žˆ๋Š” ๊ตฌ๋ฉ์˜ ๊ฐœ์ˆ˜๋ฅผ ์•Œ์•„๋ณด์ž.

์ž…๋ ฅ

์ฒซ์งธ ์ค„์— ๋ฐฉ์ถฉ๋ง ๋ณด์ˆ˜ ์Šคํ‹ฐ์ปค์˜ ํ•œ ๋ณ€์˜ ๊ธธ์ด L์ด ์ฃผ์–ด์ง„๋‹ค. L์€ ์ •์ˆ˜์ด๋‹ค. (1 ≤ L ≤ 1,000,000)

๋‘˜์งธ ์ค„์— ๊ตฌ๋ฉ์˜ ๊ฐœ์ˆ˜ K๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. (1 ≤ K ≤ 100,000)

๋‹ค์Œ K๊ฐœ์˜ ์ค„์— ๊ตฌ๋ฉ์˜ ์œ„์น˜ ์ขŒํ‘œ (y1, x1, y2, x2)๊ฐ€ ํ•œ ์ค„์— ํ•˜๋‚˜์”ฉ ์ฃผ์–ด์ง„๋‹ค. (0 ≤ y1 < y2 ≤ 1,000,000, 0 ≤ x1 x2 ≤ 1,000,000)

(y1, x1, y2, x2)๋ฅผ (y1, x1)์€ ๊ตฌ๋ฉ์˜ ์™ผ์ชฝ ์•„๋ž˜ ์ขŒํ‘œ, (y2, x2)์€ ๊ตฌ๋ฉ์˜ ์˜ค๋ฅธ์ชฝ ์œ„ ์ขŒํ‘œ๋กœ ์ •์˜ํ•œ๋‹ค. ์ฃผ์–ด์ง€๋Š” ์ขŒํ‘œ๋Š” ๋ชจ๋‘ ์ •์ˆ˜์ด๋‹ค.

๊ตฌ๋ฉ์€ ์ผ๋ถ€ ๋˜๋Š” ์ „์ฒด๊ฐ€ ๊ฒน์ณ์„œ ์กด์žฌํ•˜์ง€ ์•Š๋Š”๋‹ค. ๋˜ํ•œ ์—ฐ์†๋œ ๊ตฌ๋ฉ์„ ํ•˜๋‚˜์˜ ๊ตฌ๋ฉ์œผ๋กœ ๋ณด์ง€ ์•Š๊ณ  ๋…๋ฆฝ๋œ ๊ตฌ๋ฉ์œผ๋กœ ๋ณธ๋‹ค.

์ถœ๋ ฅ

์ฒซ์งธ ์ค„์— ๋ฐฉ์ถฉ๋ง ๋ณด์ˆ˜ ์Šคํ‹ฐ์ปค๋กœ ๋นˆํ‹ˆ์—†์ด ๋ง‰์„ ์ˆ˜ ์žˆ๋Š” ๊ตฌ๋ฉ์˜ ์ตœ๋Œ€ ๊ฐœ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค.

์˜ˆ์ œ ์ž…๋ ฅ 1

6
7
1 1 3 4
3 4 5 8
7 3 9 5
7 6 8 8
9 6 13 8
10 3 12 4
12 2 14 4

์˜ˆ์ œ ์ถœ๋ ฅ 1

4

๋ณธ๋ฌธ์˜ ๊ทธ๋ฆผ์„ ์ฐธ๊ณ ํ•˜์ž

์ถœ์ฒ˜

University > ํ•œ์–‘๋Œ€ ERICA > Zero One Algorithm Contest 2020 F๋ฒˆ