Submission #772813

#	Time	Username	Problem	Language	Result	Execution time	Memory
772813		BlockOG	Fountain (eJOI20_fountain)	Cpython 3	30 / 100	1578 ms	111696 KiB

fountain

n, q = list(map(int, input().split(" ")))

diameters = [0] * n
sum = [[0] * 20 for _ in range(n)]
for i in range(n):
    diameters[i], sum[i][0] = list(map(int, input().split(" ")))

down = [[0] * 20 for _ in range(n)]
st = [(1000000001, -1)]
for i in range(n - 1, -1, -1):
    while st[-1][0] <= diameters[i]:
        st.pop()
    down[i][0] = st[-1][1]
    st.append((diameters[i], i))

for j in range(1, 20):
    for i in range(n):
        if down[i][j - 1] == -1:
            down[i][j] = -1
            sum[i][j] = sum[i][j - 1]
        else:
            down[i][j] = down[down[i][j - 1]][j - 1]
            sum[i][j] = sum[i][j - 1] + sum[down[i][j - 1]][j - 1]

for _ in range(q):
    r, v = list(map(int, input().split(" ")))
    r -= 1

    for i in range(19, -1, -1):
        if sum[r][i] >= v: continue
        v -= sum[r][i]
        r = down[r][i]
        if r == -1: break

    print(r + 1)

• Subtask 1: 30 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40