oj.uz

답안 #772816

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
772816 2023-07-04T11:32:01 Z BlockOG Fountain (eJOI20_fountain) Python 3
30 / 100
 1500 ms 110608 KB 
import sys
input = sys.stdin.readline

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.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 2900 KB Output is correct
2 Correct 20 ms 3260 KB Output is correct
3 Correct 22 ms 3388 KB Output is correct
4 Correct 26 ms 3704 KB Output is correct
5 Correct 36 ms 3916 KB Output is correct
6 Correct 35 ms 3904 KB Output is correct
7 Correct 29 ms 3636 KB Output is correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1582 ms 110608 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 2900 KB Output is correct
2 Correct 20 ms 3260 KB Output is correct
3 Correct 22 ms 3388 KB Output is correct
4 Correct 26 ms 3704 KB Output is correct
5 Correct 36 ms 3916 KB Output is correct
6 Correct 35 ms 3904 KB Output is correct
7 Correct 29 ms 3636 KB Output is correct
8 Execution timed out 1582 ms 110608 KB Time limit exceeded
9 Halted 0 ms 0 KB -