A | B | C | D | E | F | G |
---|---|---|---|---|---|---|
AC | AC | AC | AC | - | AC | - |
F
์์ unique
์ฌ์ฉ ๊ด๋ จ ์ฝ์ง์ ํ๊ณ , E
๋ฅผ ๋ชปํ์ด์ ์์ฌ์ ๋ค. ๋ง์ฝ F
๊น์ง ๋น ๋ฅด๊ฒ ํ์์ผ๋ฉด ์๋ก์ฐ ํผํฌ๋ ๋์ค๋ ์
์ด์๋ค.
๋ฌธ์์ด ์ฌ์ด์ ๋์ด์ฐ๊ธฐ๋ฅผ ํ๋ ๋ฌธ์ ๋ค.
๊ฐ์ฅ ํฐ ์๋ณด๋ค ํ๋ ์์ ์๋ฅผ ๊ตฌํ๋ ๋ฌธ์ . set
์ ์จ์ ๋งจ ๋ค ๋ฐ๋ก ์ ์์๋ฅผ ์ถ๋ ฅํด์ฃผ๋ฉด ๋๋ค.
๋ฌธ์ ๋ฅผ ์ฝ๋ค๊ฐ ์ด๊ฑฐ ๋๋ฌด ๋์ด๋ ์๋๊ฒ C
์ ๋์จ๊ฒ ์๋๊ฐ? ํ๋ค๊ฐ ์์ธํ ๋ณด๋๊น ๊ทธ๋ฅ ์ฐ์๋ ๋ฌธ์์ด์ ๊ฐ์๋ฅผ ์ธ๋ ๋ฌธ์ ์๋ค. map
์ผ๋ก ๊ด๋ฆฌํด์ฃผ๋ฉด ์ฝ๊ฒ ํ ์ ์๋ค.
pq
๋ฅผ ์ฌ์ฉํ๋ฉด ์ฝ๊ฒ ํ ์ ์๋ ๋ฌธ์ ์ด๋ค. ์๋ ๋ฐฑ์ค ๋ฌธ์ ์ ์ ์ฌํ๋ค.
๋ฌธ์์ด์ prefix
์ suffix
์ ๋ชจ๋๋ฅผ ๋๋ ์ ํ์ด๋ณด๋ ค๊ณ ํ๋๋ฐ ์ ์๋๋ค. ๋ค์ ํ์ด๋ณผ ์์ .
bitset
์ผ๋ก ํ ์ ์๋๋ฐ, small to large
๊ฐ ์ ํด๋ผ๊ณ ํ๋ค. ๋๋ bitset
์ผ๋ก ํ์๋ค.
๋ค๋ง ๋ชจ๋ ์์์ ๋ํด bitset
์ ๋ง๋ค๋ฉด ๋ฉ๋ชจ๋ฆฌ ์ด๊ณผ๊ฐ ๋๊ฒ ๋๋ค. ์ด๋ฅผ ๋ฐฉ์งํ๊ธฐ ์ํด์๋ ํน์ ์ฌ์ด์ฆ ์ด์์ด ๋ ๋ bitset
์ผ๋ก ์ ํํ๋๋ก ํ๋ฉด ๋๋ค.
์ด ๊ณผ์ ์์ ์ด์ vector
-> bitset
์ผ๋ก ์ ํ๋๋๋ฐ, stack์ ์ฌ์ฉํด์ ์ฌ์ฉ๋์ง ์๋ bitset
์ ๊พธ์คํ ์ง์์ฃผ๋ฉด์ ํ ๋นํ๋ฉด ํ์ด๊ฐ ๊ฐ๋ฅํ๋ค. ๋์ถฉ ์๋์ ๊ฐ์ ๋๋์ผ๋ก ํ ๋นํ๋ค.
vector<bitset<200001>> bs(20000);vector<int> s[200010];stack<int> deleted;int bsCnt;int newBs() {if (deleted.size() == 0) {if (bsCnt >= 20000) assert("MEM OVERFLOW!");return bsCnt++;}int ret = deleted.top(); deleted.pop();bs[ret].reset();return ret;}
๊ทธ๋ฆฌ๊ณ , vector
์ unique
๋ฅผ ์ฌ์ฉํด์ ์ค๋ณต์์๋ฅผ ์ ๊ฑฐํ ๋๋ sorted vector
์์๋ง ์ฌ์ฉํด์ผ ํจ์ ์ ์ํ์. ์ฆ, unique
๋ ์๋์ฒ๋ผ ์ฌ์ฉํ๋๊ฒ ์ ์์ด๋ค. ์ด๊ฑธ ๋์ณ์ 6๋ฒ ํ๋ ธ๋ค..
sort(v.begin(), v.end());v.erase(unique(v.begin(), v.end()), v.end());
๋ง์ง๋ง์ผ๋ก bitset
์ ๋ํ method
๋ฅผ ์ ๋ฆฌํ๋ค.
Editorial์ ํ์ธํด๋ณด๋ฉด, ๊ณต์ด ์ด๋ํ๊ฒ ๋๋ฉด ๊ฒฐ๊ณผ์ ์ผ๋ก 2๋ฐฐ ์ด์์ size
๋ก ํ ๋น๋๊ฒ ๋๋ฏ๋ก, ํ ์ฟผ๋ฆฌ๊ฐ ์ ์ํ์ด ๋๋ ๊ผด์ด๋ผ๊ณ ํ๋ค. ๊ทธ๋์ swap
์ด๋ move
๋ฅผ ์ฐ๋ฉด, ์ ํด๊ฒฐ์ด ๋๋ ๋ชจ์์ด๋ค. ์๋๊ฐ ์ ํด. STL๋ก ๊ฐ๋ฅํ๊ฒ ๋๋ ๊ฒ์ด๊ณ , ์์ ์ญ๋ฐฐ ํด์ผํ๋ค.
Skip