๋ฌธ์
https://www.acmicpc.net/problem/21944
๋ฐฑ์ค ๋ฌธ์ ์ง - 0x16๊ฐ - ์ด์ง ๊ฒ์ ํธ๋ฆฌ
์๊ณ ๋ฆฌ์ฆ: ์ด์ง ํ์ ํธ๋ฆฌ, ํธ๋ฆฌ๋ฅผ ์ฌ์ฉํ ์งํฉ๊ณผ ๋งต
ํ์ด

21939: ๋ฌธ์ ์ถ์ฒ ์์คํ
Version 1 ๊ณผ ๋น์ทํ๊ฒ ํ๊ณ ๋ฌดํ TLEโพ๏ธ์ ๋น ์ก๋ ๋ฌธ์ ๋ค.
์ข ๋ ๋ฌด์ํ๊ฒ(?) ํ์ด์ผ AC๋ฅผ ๋ฐ์ ์ ์๋ค.
์ผ๋จ ๋ฌธ์ ์ ์กฐ๊ฑด์ ์ ๋ฆฌํด๋ณด๋ฉด ๋ค์๊ณผ ๊ฐ๋ค.
์ ๋ ฅ ๋ฐ์ดํฐ ๋ฒ์: 1 <= ์๊ณ ๋ฆฌ์ฆ, ๋์ด๋ <= 100, 1 <= ๋ฌธ์ ๋ฒํธ <= 100,000
recommend: ์๊ณ ๋ฆฌ์ฆ ๋ถ๋ฅ๊ฐ G์ธ ๋ฌธ์
- ๋์ด๋ ๋๊ณ , ๋ฒํธ๊ฐ ํฐ ๋ฌธ์
- ๋์ด๋ ๋ฎ๊ณ , ๋ฒํธ๊ฐ ์์ ๋ฌธ์
recommend2: ์๊ณ ๋ฆฌ์ฆ ์๊ด X
- ๋์ด๋ ๋๊ณ , ๋ฒํธ๊ฐ ํฐ ๋ฌธ์
- ๋์ด๋ ๋ฎ๊ณ , ๋ฒํธ๊ฐ ์์ ๋ฌธ์
recommend3: ๋์ด๋ L ์ด์/๋ฏธ๋ง์ธ ๋ฌธ์ , ์๊ณ ๋ฆฌ์ฆ ์๊ด X
- L ์ด์: ๋ฒํธ๊ฐ ์์ ๋ฌธ์
- L ๋ฏธ๋ง: ๋ฒํธ๊ฐ ํฐ ๋ฌธ์
๐ ์๊ณ ๋ฆฌ์ฆ๋ณ ์ต๋/์ต์, ๋์ด๋๋ณ ์ต๋/์ต์, ๋ฌธ์ ์ ์ ๋ณด(๋ฒํธ, ๋์ด๋, ์๊ณ ๋ฆฌ์ฆ)์ด ํ์ํ ์ํ
๋ฌธ์ ์ ์ ๋ณด์ ๋์ด๋๋ณ ์ต๋/์ต์๋ ๋ฆฌ์คํธ๋ฅผ, ์๊ณ ๋ฆฌ์ฆ๋ณ ์ต๋/์ต์๋ ๋์
๋๋ฆฌ๋ฅผ ์ฌ์ฉํ๋ค.
์๊ณ ๋ฆฌ์ฆ ๊ฐ์ ๊ฒฝ์ฐ G์ ํด๋น๋๋ ๋ฌธ์ ๋ค๋ง ํ์ํ๋ฉด ๋์ง๋ง, ๋์ด๋๋ ์กฐ๊ฑด๊ฐ์ด ๋ช
ํํ ์ ํด์ ธ์์ง ์๊ธฐ ๋๋ฌธ์ด๋ค.
๋ช
๋ น ์กฐ๊ฑด์ ์๋ง์ ๋ฌธ์ ๋ฅผ ์ฐพ์๋๊น์ง ๋์ด๋ ๋์→๋ฎ์ or ๋ฎ์→๋์ ์์ผ๋ก ํ์ํด์ผํ๋ค.
๋ฐ๋ผ์ ์๋์ ๊ฐ์ด ์ด๊ธฐํํด์ค ๋ค ์งํํ๋ค.
๋์ด๋๋ณ ์ต๋/์ต์ - ๋ฒ์(1 ~ 100)๋ฅผ ๊ฐ์ ํ 2์ฐจ์ ๋ฆฌ์คํธ
์๊ณ ๋ฆฌ์ฆ๋ณ ์ต๋/์ต์ - ๋์
๋๋ฆฌ
๋ฌธ์ ์ ์ ๋ณด - ๋ฒ์(1 ~ 100000)๋ฅผ ๊ฐ์ ํ 2์ฐจ์ ๋ฆฌ์คํธ
# ๋์ด๋๋ณ ํ
l_max = [[] for _ in range(101)] # ์ต๋ํ
l_min = [[] for _ in range(101)] # ์ต์ํ
# ๊ทธ๋ฃน๋ณ ํ
g_max = {} # ์ต๋ํ - ํ์ํ ๋๋ง ์์ฑ
g_min = {} # ์ต์ํ - ํ์ํ ๋๋ง ์์ฑ
# ๋ฌธ์ ์ ๋ณด๋ฅผ O(1)์ ์ ๊ทผํ๊ธฐ ์ํ ๋ฐฐ์ด
problems = [0] * 100001 # [๋์ด๋, ๊ทธ๋ฃน] ์ ์ฅ
problems์ ๋ฌธ์ ์ ์ ๋ณด๊ฐ ์ ์ฅ๋์ด์์ผ๋ฏ๋ก ๋์ด๋๋ณ ํ์๋ ๋ฌธ์ ์ ๋ฒํธ๋ง ์ ์ฅ- ์๊ณ ๋ฆฌ์ฆ์ ๋์ด๋, ๋ฌธ์ ์ ๋ฒํธ๋ฅผ ๋ชจ๋ ๋ฐ์ ธ์ผํ๋ฏ๋ก (๋์ด๋, ๋ฌธ์ ๋ฒํธ)๋ก ์ ์ฅ
๋ฌธ์ ๋ฐ์ดํฐ๋ฅผ ์ง์ด๋ฃ์ผ๋ฉด ์๋์ ๊ฐ์ ํํ๊ฐ ๋๋ค.
๋์ด๋๋ณ ์ต๋ํ = [[-๋ฌธ์ ๋ฒํธ1], [-๋ฌธ์ ๋ฒํธ2]...]
๋์ด๋๋ณ ์ต์ํ = [[๋ฌธ์ ๋ฒํธ1], [๋ฌธ์ ๋ฒํธ2]...]
์๊ณ ๋ฆฌ์ฆ๋ณ ์ต๋ํ = {์๊ณ ๋ฆฌ์ฆ1: [(-๋์ด๋, -๋ฌธ์ ๋ฒํธ)]...}
์๊ณ ๋ฆฌ์ฆ๋ณ ์ต์ํ = {์๊ณ ๋ฆฌ์ฆ1: [(๋์ด๋, ๋ฌธ์ ๋ฒํธ)]...}
๋ฌธ์ ์ ์ ๋ณด[๋ฌธ์ ๋ฒํธ] = [[๋์ด๋, ์๊ณ ๋ฆฌ์ฆ]...]
add๋ ์ ํํ ๊ทธ๋๋ก ์งํ, solved๋ ํด๋น ๋ฌธ์ ์ ๊ฐ์ 0์ผ๋ก ๋ณ๊ฒฝํด์ค๋ค. (ํ์๋ ์ด์ ์ ๋ณด๊ฐ ๊ทธ๋๋ก ๋จ์์๋ ์ํ)
๊ทธ๋ฆฌ๊ณ ๋ฉ์ธ ํฌ์ธํธ์ธ recommend ~ 3 ๋ ์กฐ๊ฑด๋ถ๊ธฐ๋ฅผ ๋ช ํํ ์์ฑํด์ค์ผํ๋ค.
recommend
- ํ[G]๊ฐ ๋จ์์์๋๊น์ง ์งํ
- ํ์์ popํ ๊ฐ โก๏ธ L, P
- P์ ๊ฐ์ด 0์ด๊ฑฐ๋ ์ ์ฅ๋์ด์๋ ๊ฐ๊ณผ [L, G]๊ฐ ๋ค๋ฅผ๊ฒฝ์ฐ โก๏ธ ์ด๋ฏธ solved๋๊ฑฐ๋ ๋ณ๊ฒฝ๋ ๋ฌธ์ ์ด๋ฏ๋ก continue
- ์ํ๋ ๊ฐ์ ์ฐพ์๋ค๋ฉด ์ถ๋ ฅ, ๋ค์ ํ์ ์ถ๊ฐํ๊ณ break
recommed2
- ๊ฐ์ ๋ชป์ฐพ์์ ๊ฒฝ์ฐ๋ฅผ ํ๋จํ๊ธฐ ์ํด ํ๋๊ทธ ์ค์ โก๏ธ found = False
- ์ต๋/์ต์์ ๋ฐ๋ผ ๋ฒ์ ์ค์ ํ ๋์ด๋๋ณ๋ก ํ๋์ฉ ํ์ (1 ~ 100 or 100 ~ 1)
- ํด๋น ๋์ด๋ L์ ํ์ด ๋จ์์์๋๊น์ง ํ์
- ํ์์ popํ ๊ฐ โก๏ธ P
- P์ ๊ฐ์ด 0์ด๊ฑฐ๋ ์ ์ฅ๋์ด์๋ ๊ฐ๊ณผ L์ด ๋ค๋ฅผ๊ฒฝ์ฐ โก๏ธ ์ด๋ฏธ solved๋๊ฑฐ๋ ๋ณ๊ฒฝ๋ ๋ฌธ์ ์ด๋ฏ๋ก continue
- ์ํ๋ ๊ฐ์ ์ฐพ์๋ค๋ฉด ์ถ๋ ฅ, ๋ค์ ํ์ ์ถ๊ฐ
- ํ๋๊ทธ๋ฅผ True๋ก ๋ณ๊ฒฝ ํ break
- ๋ชจ๋ ํ์์ด ๋๋ํ์๋ ํ๋๊ทธ๊ฐ False๋ผ๋ฉด -1 ์ถ๋ ฅ
recommend3
- ๊ฐ์ ๋ชป์ฐพ์์ ๊ฒฝ์ฐ๋ฅผ ํ๋จํ๊ธฐ ์ํด ํ๋๊ทธ ์ค์ โก๏ธ found = False
- L๋ถํฐ or L๊น์ง๋ก ๋ฒ์ ์ค์ ํ ๋์ด๋๋ณ๋ก ํ๋์ฉ ํ์ (L ~ 100 or 1 ~ L-1)
- ํด๋น ๋์ด๋์ ํ์ด ๋จ์์์๋๊น์ง ํ์
- ํ์์ popํ ๊ฐ โก๏ธ P
- P์ ๊ฐ์ด 0์ด๊ฑฐ๋ ์ ์ฅ๋์ด์๋ ๊ฐ๊ณผ ๋ค๋ฅผ๊ฒฝ์ฐ โก๏ธ ์ด๋ฏธ solved๋๊ฑฐ๋ ๋ณ๊ฒฝ๋ ๋ฌธ์ ์ด๋ฏ๋ก continue
- ์ํ๋ ๊ฐ์ ์ฐพ์๋ค๋ฉด ์ถ๋ ฅ, ๋ค์ ํ์ ์ถ๊ฐ
- ํ๋๊ทธ๋ฅผ True๋ก ๋ณ๊ฒฝ ํ break
- ๋ชจ๋ ํ์์ด ๋๋ํ์๋ ํ๋๊ทธ๊ฐ False๋ผ๋ฉด -1 ์ถ๋ ฅ
์ ์ฒด ์ฝ๋
# ๋ฉ๋ชจ๋ฆฌ: 73604KB / ์๊ฐ: 416ms
from sys import stdin
from heapq import heappush, heappop
input = stdin.readline
# ๋์ด๋๋ณ ํ
l_max = [[] for _ in range(101)] # ์ต๋ํ
l_min = [[] for _ in range(101)] # ์ต์ํ
# ๊ทธ๋ฃน๋ณ ํ
g_max = {} # ์ต๋ํ - ํ์ํ ๋๋ง ์์ฑ
g_min = {} # ์ต์ํ - ํ์ํ ๋๋ง ์์ฑ
# ๋ฌธ์ ์ ๋ณด๋ฅผ O(1)์ ์ ๊ทผํ๊ธฐ ์ํ ๋ฐฐ์ด
problems = [0] * 100001 # [๋์ด๋, ๊ทธ๋ฃน] ์ ์ฅ
# ์ฃผ์ด์ง ๋ฌธ์ ๋ถํฐ ์ฒ๋ฆฌ
N = int(input())
for _ in range(N):
P, L, G = map(int, input().split())
problems[P] = [L, G] # ๋ฌธ์ ์ ๋ณด ์ ์ฅ
# ๋์ด๋๋ณ ํ์ ์ถ๊ฐ
heappush(l_max[L], -P)
heappush(l_min[L], P)
# ๊ทธ๋ฃน๋ณ ํ์ ์ถ๊ฐ
if G not in g_max:
g_max[G] = []
g_min[G] = []
heappush(g_max[G], (-L, -P))
heappush(g_min[G], (L, P))
# ๋ช
๋ น๋๋ก ์ฒ๋ฆฌ
M = int(input())
for _ in range(M):
cmd, *data = input().rstrip().split()
# 1. add
if cmd == "add":
P, L, G = map(int, data)
problems[P] = [L, G] # ๋ฌธ์ ์ ๋ณด ์ ์ฅ
heappush(l_max[L], -P)
heappush(l_min[L], P)
if G not in g_max:
g_max[G] = []
g_min[G] = []
heappush(g_max[G], (-L, -P))
heappush(g_min[G], (L, P))
# 2. solved
elif cmd == "solved":
P = int(data[0])
problems[P] = 0 # ๋ฌธ์ ์ญ์ ํ์
# 3-1. recommend
elif cmd == "recommend":
G, x = map(int, data)
if x == 1:
while g_max[G]:
L, P = heappop(g_max[G])
P = -P
# ์ญ์ ๋๊ฑฐ๋ ์ ๋ณด๊ฐ ๋ณ๊ฒฝ๋ ๊ฒฝ์ฐ
if not problems[P] or problems[P] != [-L, G]:
continue
print(P)
heappush(g_max[G], (L, -P))
break
else:
while g_min[G]:
L, P = heappop(g_min[G])
if not problems[P] or problems[P] != [L, G]:
continue
print(P)
heappush(g_min[G], (L, P))
break
# 3-2. recommend2
elif cmd == "recommend2":
x = int(data[0])
found = False
if x == 1:
for L in range(100, -1, -1):
while l_max[L]:
P = -heappop(l_max[L])
if not problems[P] or problems[P][0] != L:
continue
print(P)
heappush(l_max[L], -P)
found = True
break
if found:
break
else:
for L in range(101):
while l_min[L]:
P = heappop(l_min[L])
if not problems[P] or problems[P][0] != L:
continue
print(P)
heappush(l_min[L], P)
found = True
break
if found:
break
# 3-3. recommend3
else:
x, L = map(int, data)
found = False
if x == 1:
for i in range(L, 101):
while l_min[i]:
P = heappop(l_min[i])
if not problems[P] or problems[P][0] != i:
continue
print(P)
heappush(l_min[i], P)
found = True
break
if found:
break
else:
for i in range(L-1, -1, -1):
while l_max[i]:
P = -heappop(l_max[i])
if not problems[P] or problems[P][0] != i:
continue
print(P)
heappush(l_max[i], -P)
found = True
break
if found:
break
if not found:
print(-1)
๋ฐ์ดํฐ ๊ด๋ฆฌ ๋ฐฉ์์ด ๊ด๊ฑด์ธ ๋ฌธ์ ์๋ค. ์ฌ์ค ์ด ๋ฐฉ๋ฒ(์ฌ๋ฌ๊ฐ์ ํ ๋ชจ์์ผ๋ก ๊ด๋ฆฌ)์ ๋ ์ฌ๋ฆฌ๊ธด ํ์๋๋ฐ... ์ง์ง ๋๋์ค์ ๋ชฐ๋๋ค^^;;
๊ฒฐ๊ตญ ๋ค๋ฅธ ๋ถ์ ํ์ด๋ฅผ ์ฐธ๊ณ ํด์ ํ๊ธด ํ์ง๋ง ์์ด ๋ค ํ๋ จํ๋ค. ์๊ฐ์ด๊ณผ์ ๋ช์ ์์ํ ๊ฐํ ์ค ์์๋ค