提出 #859019


ソースコード 拡げる

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)

提出情報

提出日時
問題 E - 高橋君とホテル
ユーザ yugamiakira
言語 PyPy2 (5.6.0)
得点 700
コード長 800 Byte
結果 AC
実行時間 2920 ms
メモリ 60328 KB

ジャッジ結果

セット名 Sample Subtask1 All
得点 / 配点 0 / 0 200 / 200 500 / 500
結果
AC × 1
AC × 14
AC × 27
セット名 テストケース
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
ケース名 結果 実行時間 メモリ
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