정올/KOI기출 문제

아이템 획득

juwanseo 2025. 4. 20. 11:22
from bisect import bisect_left, bisect_right

mii = lambda: map(int, input().split())
N, Q = mii()
T = 200_001

xa = [[] for _ in range(T)]
ya = [[] for _ in range(T)]

for _ in range(N):
    x, y, w = mii()
    xa[x].append((y, w))
    ya[y].append((x, w))

def make_list(arr, pos, total):
    arr.sort()
    t = 0
    for p, items in arr:
        pos.append(p)
        t += items
        total.append(t)

xp = [[] for _ in range(T)]
yp = [[] for _ in range(T)]
xt = [[] for _ in range(T)]
yt = [[] for _ in range(T)]

for i in range(T):
    make_list(xa[i], xp[i], xt[i])
    make_list(ya[i], yp[i], yt[i])

def get_items(pos, total, left, right):
    start = bisect_left(pos, left)
    end = bisect_right(pos, right) - 1

    if end < start:
        return 0
    res = total[end]
    if start > 0:
        res -= total[start - 1]
    return res

x, y, ans = 1, 1, 0
for _ in range(Q):
    d, v = mii()
    if d == 0:
        ans += get_items(yp[y], yt[y], x + 1, x + v)
        x += v
    elif d == 1:
        ans += get_items(xp[x], xt[x], y + 1, y + v)
        y += v
    elif d == 2:
        ans += get_items(yp[y], yt[y], x - v, x - 1)
        x -= v
    elif d == 3:
        ans += get_items(xp[x], xt[x], y - v, y - 1)
        y -= v

print(ans)

'정올 > KOI기출 문제' 카테고리의 다른 글

양팔저울  (0) 2025.04.24
햄버거 분배  (0) 2025.04.20
정올 2566 KOI 2012 - 오븐 시계  (0) 2025.02.19
정올 2911 KOI 2015 - 사과  (0) 2025.02.13
정올 3333 KOI 2019 - 막대기  (0) 2025.02.06