Submission #859019


Source Code Expand

Copy
import bisect

n=int(raw_input())
x=map(int,raw_input().split())+[float('inf')]
l=int(raw_input())
q=int(raw_input())
r=[[0]*20 for _ in xrange(n)]

for i in xrange(n):
    if x[i]+l==x[bisect.bisect_left(x,x[i]+l)]:
        r[i][0]=bisect.bisect_left(x,x[i]+l)
    else:
        r[i][0]=bisect.bisect_left(x,x[i]+l)-1

for k in xrange(19):
    for i in xrange(n):
        r[i][k+1]=r[r[i][k]][k]
        
for i in xrange(q):
    a,b=map(int,raw_input().split())
    a-=1
    b-=1
    ans=0
    if a>b:
        a,b=b,a
    while 1:
        if bisect.bisect_left(r[a],b)>=1:
            ans+=1<<(bisect.bisect_left(r[a],b)-1)
            a=r[a][bisect.bisect_left(r[a],b)-1]
        else :
            ans+=1<<bisect.bisect_left(r[a],b)
            break
    print(ans)

Submission Info

Submission Time
Task E - Tak and Hotels
User yugamiakira
Language PyPy2 (5.6.0)
Score 700
Code Size 800 Byte
Status AC
Exec Time 2920 ms
Memory 60328 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 200 / 200 500 / 500
Status
AC × 1
AC × 14
AC × 27
Set Name Test Cases
Sample example_01.txt
Subtask1 example_01.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt
All example_01.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt
Case Name Status Exec Time Memory
example_01.txt AC 60 ms 8944 KB
subtask1_01.txt AC 75 ms 9200 KB
subtask1_02.txt AC 64 ms 8944 KB
subtask1_03.txt AC 226 ms 19820 KB
subtask1_04.txt AC 213 ms 19820 KB
subtask1_05.txt AC 255 ms 18928 KB
subtask1_06.txt AC 194 ms 20376 KB
subtask1_07.txt AC 128 ms 11120 KB
subtask1_08.txt AC 162 ms 11888 KB
subtask1_09.txt AC 192 ms 17648 KB
subtask1_10.txt AC 200 ms 16496 KB
subtask1_11.txt AC 214 ms 19820 KB
subtask1_12.txt AC 187 ms 16624 KB
subtask1_13.txt AC 198 ms 19692 KB
subtask2_01.txt AC 2633 ms 53168 KB
subtask2_02.txt AC 2876 ms 54048 KB
subtask2_03.txt AC 2558 ms 53152 KB
subtask2_04.txt AC 1097 ms 42476 KB
subtask2_05.txt AC 1784 ms 46060 KB
subtask2_06.txt AC 1577 ms 52768 KB
subtask2_07.txt AC 2629 ms 53920 KB
subtask2_08.txt AC 2920 ms 53352 KB
subtask2_09.txt AC 2865 ms 53656 KB
subtask2_10.txt AC 2919 ms 53760 KB
subtask2_11.txt AC 2851 ms 51784 KB
subtask2_12.txt AC 2354 ms 53648 KB
subtask2_13.txt AC 1702 ms 60328 KB