| ์๊ฐ ์ ํ | ๋ฉ๋ชจ๋ฆฌ ์ ํ | ์ ์ถ | ์ ๋ต | ๋งํ ์ฌ๋ | ์ ๋ต ๋น์จ |
|---|---|---|---|---|---|
| 3 ์ด | 1024 MB | 287 | 51 | 42 | 22.951% |
๋ฌ์คํฐ์ ๋๋๐ฉ ๊ฐ๊ฒ์๋ $1$๋ฒ๋ถํฐ $N$๋ฒ๊น์ง์ ๋๋ ๋ฐ์ฃฝ ๊ธฐ๊ณ $N$๊ฐ๊ฐ ์๋ค. ๊ฐ ๋๋ ๋ฐ์ฃฝ ๊ธฐ๊ณ์๋ ๋๋ ๋ฐ์ฃฝ์ด ํ๋์ฉ ๋ค์ด ์๋ค. ๊ฐ ๋๋ ๋ฐ์ฃฝ์ ์ฌ๋ฌ ๊ฐ์ง ๋ง์ ๊ฐ์ง ์ ์๋๋ฐ, ๋ง์ $1$ ์ด์ $10^9$ ์ดํ์ ์ ์๋ก ํํํ ์ ์๋ค. ์๋ก ๋ค๋ฅธ ๋ ๋๋ ๋ฐ์ฃฝ์ ํฉ์น ์ ์๋ค. ํฉ์ณ์ง ๋ฐ์ฃฝ์ด ๊ฐ์ง ๋ง์ ์งํฉ์ ๋ ๋ฐ์ฃฝ์ด ๊ฐ์ง ๋ง์ ํฉ์งํฉ์ด๋ค. ์ฌ๋ฌ๋ถ์ ์ฒ์ ๋๋ ๋ฐ์ฃฝ์ด ๊ฐ์ง ๋ง์ ๋ฒ์๊ฐ ์ฃผ์ด์ง ๋ ๋ฌ์คํฐ์ ๋ฐ์ฃฝ ๊ณผ์ ์ ๋ฐ๋ผ ์๋ ๋ช ๋ น์ $Q$๋ฒ ์ํํด์ผ ํ๋ค.
1 a b: $a$๋ฒ ๊ธฐ๊ณ์ ๋ ๋ฐ์ฃฝ๊ณผ $b$๋ฒ ๊ธฐ๊ณ์ ๋ ๋ฐ์ฃฝ์ ๋จ๊น์์ด ์น์น ๊ธ์ ํ ๋ชจ๋ ํฉ์ณ $a$๋ฒ ๊ธฐ๊ณ์ ๋ฃ๋๋ค.2 a: $a$๋ฒ ๊ธฐ๊ณ์ ๋ ๋ฐ์ฃฝ์ด ๊ฐ์ง ๋ง์ ๊ฐ์๋ฅผ ์ถ๋ ฅํ๋ค.์ฒซ์งธ ์ค์ ๋๋ ๋ฐ์ฃฝ ๊ธฐ๊ณ์ ์ $N$์ ๋ช ๋ น์ ์ $Q$๊ฐ ๊ณต๋ฐฑ์ผ๋ก ๊ตฌ๋ถ๋์ด ์ฃผ์ด์ง๋ค. $(1 \le N, Q \le 200\,000)$
๋ค์ $N$๊ฐ ์ค์ ๊ฑธ์ณ ๋๋ ๋ฐ์ฃฝ ๊ธฐ๊ณ์ ๋ ๋๋ ๋ฐ์ฃฝ์ ๋ง์ ๋ฒ์๊ฐ ์ฃผ์ด์ง๋ค. ๊ทธ์ค $i$๋ฒ์งธ ์ค์๋ ์ ์ $\ell_i$, $r_i$๊ฐ ๊ณต๋ฐฑ์ผ๋ก ๊ตฌ๋ถ๋์ด ์ฃผ์ด์ง๋ค. ์ด๋ $i$๋ฒ ๋๋ ๋ฐ์ฃฝ ๊ธฐ๊ณ์ ๋ ๋ฐ์ฃฝ์ ๋ง์ $\ell_i$ ์ด์ $r_i$ ์ดํ์ ๋ชจ๋ ์ ์๊ฐ ํฌํจ๋๋ค๋ ๋ป์ด๋ค. $(1 \le \ell_i \le r_i \le 10^9)$
๋ค์ $Q$๊ฐ ์ค์ ๊ฑธ์ณ ๋ช ๋ น์ด ์ฃผ์ด์ง๋ค. ๊ฐ ๋ช ๋ น์ ์๋ ํ์ ์ค ํ๋๋ก ์ฃผ์ด์ง๋ค.
1 a b: $a$๋ฒ ๊ธฐ๊ณ์ ๋ ๋ฐ์ฃฝ๊ณผ $b$๋ฒ ๊ธฐ๊ณ์ ๋ ๋ฐ์ฃฝ์ ๋จ๊น์์ด ์น์น ๊ธ์ ํ ๋ชจ๋ ํฉ์ณ $a$๋ฒ ๊ธฐ๊ณ์ ๋ฃ๋๋ค. $a$๋ฒ ๊ธฐ๊ณ์ $b$๋ฒ ๊ธฐ๊ณ์ ๋ฐ์ฃฝ์ด ๋จ์ ์๋ ๊ฒฝ์ฐ๋ง ์ฃผ์ด์ง๋ค. $(1 \le a, b \le N;$ $a \ne b)$2 a: $a$๋ฒ ๊ธฐ๊ณ์ ๋ ๋ฐ์ฃฝ์ด ๊ฐ์ง ๋ง์ ๊ฐ์๋ฅผ ์ถ๋ ฅํ๋ค. $a$๋ฒ ๊ธฐ๊ณ์ ๋ฐ์ฃฝ์ด ๋จ์ ์๋ ๊ฒฝ์ฐ๋ง ์ฃผ์ด์ง๋ค. $(1 \le a \le N)$2๋ฒ ๋ช ๋ น์ ํ๋ ์ด์ ์ฃผ์ด์ง๋ค.
2๋ฒ ๋ช ๋ น์ด ์ฃผ์ด์ง ๋๋ง๋ค $a$๋ฒ ๊ธฐ๊ณ์ ๋ ๋ฐ์ฃฝ์ด ๊ฐ์ง ๋ง์ ์๋ฅผ ํ ์ค์ ์ถ๋ ฅํ๋ค.
3 7 1 3 2 4 6 8 2 1 2 2 2 3 1 1 3 2 1 1 2 1 2 2
3 3 3 6 7
์ฒ์์ $1$๋ฒ ๊ธฐ๊ณ์๋ $\{1, 2, 3\}$, $2$๋ฒ ๊ธฐ๊ณ์๋ $\{2, 3, 4\}$, $3$๋ฒ ๊ธฐ๊ณ์๋ $\{6, 7, 8\}$์ ๋ง์ ๊ฐ์ง ๋ฐ์ฃฝ์ด ๋ค์ด ์๋ค.
๋ค ๋ฒ์งธ ๋ช ๋ น์์ $1$๋ฒ๊ณผ $3$๋ฒ ๊ธฐ๊ณ์ ๋ ๋ฐ์ฃฝ์ ํฉ์น ๋ค, $1$๋ฒ ๊ธฐ๊ณ์๋ $\{1, 2, 3, 6, 7, 8\}$์ ๋ง์ ๊ฐ์ง ๋ฐ์ฃฝ์ด ๋ค์ด ์๋ค.
์ฌ์ฏ ๋ฒ์งธ ๋ช ๋ น์์ $2$๋ฒ๊ณผ $1$๋ฒ ๊ธฐ๊ณ์ ๋ ๋ฐ์ฃฝ์ ํฉ์น ๋ค, $2$๋ฒ ๊ธฐ๊ณ์๋ $\{1, 2, 3, 4, 6, 7, 8\}$์ ๋ง์ ๊ฐ์ง ๋ฐ์ฃฝ์ด ๋ค์ด ์๋ค.
Contest > BOJ User Contest > ์๊ฐ ํฅ์ ํ > ์๊ฐ ํฅ์ ํ 2024. 07. C๋ฒ