oj.uz

Submission #772813

# Submission time Handle Problem Language Result Execution time Memory
772813 2023-07-04T11:30:21 Z BlockOG Fountain (eJOI20_fountain) Python 3
30 / 100
 1500 ms 111696 KB 
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

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2900 KB Output is correct
2 Correct 23 ms 3268 KB Output is correct
3 Correct 23 ms 3404 KB Output is correct
4 Correct 30 ms 3484 KB Output is correct
5 Correct 37 ms 3784 KB Output is correct
6 Correct 42 ms 3764 KB Output is correct
7 Correct 33 ms 3512 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1578 ms 111696 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2900 KB Output is correct
2 Correct 23 ms 3268 KB Output is correct
3 Correct 23 ms 3404 KB Output is correct
4 Correct 30 ms 3484 KB Output is correct
5 Correct 37 ms 3784 KB Output is correct
6 Correct 42 ms 3764 KB Output is correct
7 Correct 33 ms 3512 KB Output is correct
8 Execution timed out 1578 ms 111696 KB Time limit exceeded
9 Halted 0 ms 0 KB -