結果

問題 No.3101 Range Eratosthenes Query
コンテスト
ユーザー moon17
提出日時 2025-04-11 23:06:04
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,006 bytes
コンパイル時間 341 ms
コンパイル使用メモリ 82,232 KB
実行使用メモリ 634,380 KB
最終ジャッジ日時 2025-04-11 23:06:14
合計ジャッジ時間 9,946 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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

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

# 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

N=len(s)
A=s[:]
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])
for l,r in e:
  if l==1:
    ans=1
  else:
    ans=query1(N0,data,l,r+1,l)
  print(ans)
0