結果

問題 No.3101 Range Eratosthenes Query
ユーザー moon17
提出日時 2025-04-11 22:56:21
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,108 bytes
コンパイル時間 900 ms
コンパイル使用メモリ 82,724 KB
実行使用メモリ 1,136,480 KB
最終ジャッジ日時 2025-04-11 22:56:31
合計ジャッジ時間 9,459 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample MLE * 1 -- * 1
other -- * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

(q,),*e=[[*map(int,s.split())]for s in open(0)]
def spf(n):
 spf=[*range(n+1)]
 for i in range(2,n+1):
  for j in range(i*2,n+1,i):
   spf[j]=i
 return spf
s=spf(10**6)
for i in range(10**6+1):
  if s[i]==i:
    s[i]=0
s[0]=s[1]=1<<60

#https://tjkendev.github.io/procon-library/python/range_query/merge-sort-tree.html
from bisect import bisect
from heapq import merge

def construct(N, A):
    N0 = 2**(N-1).bit_length()
    data = [None]*(2*N0)
    for i, a in enumerate(A):
        data[N0-1+i] = [a]
    for i in range(N, N0):
        data[N0-1+i] = []
    for i in range(N0-2, -1, -1):
        *data[i], = merge(data[2*i+1], data[2*i+2])
    return N0, data

# count elements A_i s.t. A_i <= k for i in [l, r)
def query1(N0, data, l, r, k):
    L = l + N0; R = r + N0
    s = 0
    while L < R:
        if R & 1:
            R -= 1
            s += bisect(data[R-1], k-1)
        if L & 1:
            s += bisect(data[L-1], k-1)
            L += 1
        L >>= 1; R >>= 1
    return s

n0,data=construct(len(s),s)
for l,r in e:
  if l==1:
    ans=1
  else:
    ans=query1(n0,data,l,r+1,l)
  print(ans)
0