Submission #859000


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
    if a>b:
        a,b=b,a
    while 1:
        #print bisect.bisect_left(r[a],b),r[a]
        if b==r[a][bisect.bisect_left(r[a],b)]:
            print(1<<bisect.bisect_left(r[a],b))
            break
        else:
            a=r[a][bisect.bisect_left(r[a],b)-1]

Submission Info

Submission Time
Task E - Tak and Hotels
User yugamiakira
Language PyPy2 (5.6.0)
Score 0
Code Size 768 Byte
Status WA
Exec Time 3166 ms
Memory 53024 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 0 / 200 0 / 500
Status
AC × 1
AC × 2
WA × 2
TLE × 10
AC × 2
WA × 3
TLE × 22
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 83 ms 9712 KB
subtask1_01.txt TLE 3161 ms 16364 KB
subtask1_02.txt AC 64 ms 8944 KB
subtask1_03.txt TLE 3157 ms 17772 KB
subtask1_04.txt WA 261 ms 20336 KB
subtask1_05.txt TLE 3157 ms 17772 KB
subtask1_06.txt WA 139 ms 11760 KB
subtask1_07.txt TLE 3160 ms 17260 KB
subtask1_08.txt TLE 3157 ms 17772 KB
subtask1_09.txt TLE 3161 ms 17900 KB
subtask1_10.txt TLE 3161 ms 17900 KB
subtask1_11.txt TLE 3161 ms 17900 KB
subtask1_12.txt TLE 3161 ms 17900 KB
subtask1_13.txt TLE 3157 ms 17772 KB
subtask2_01.txt TLE 3166 ms 47920 KB
subtask2_02.txt WA 2525 ms 53024 KB
subtask2_03.txt TLE 3162 ms 48672 KB
subtask2_04.txt TLE 3164 ms 37740 KB
subtask2_05.txt TLE 3164 ms 38764 KB
subtask2_06.txt TLE 3162 ms 47648 KB
subtask2_07.txt TLE 3166 ms 48672 KB
subtask2_08.txt TLE 3166 ms 47976 KB
subtask2_09.txt TLE 3162 ms 48280 KB
subtask2_10.txt TLE 3162 ms 48256 KB
subtask2_11.txt TLE 3162 ms 46408 KB
subtask2_12.txt TLE 3162 ms 48400 KB
subtask2_13.txt TLE 3166 ms 48552 KB