結果

問題 No.3101 Range Eratosthenes Query
コンテスト
ユーザー moon17
提出日時 2025-04-11 22:27:59
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 901 bytes
コンパイル時間 400 ms
コンパイル使用メモリ 82,572 KB
実行使用メモリ 67,456 KB
最終ジャッジ日時 2025-04-11 22:28:10
合計ジャッジ時間 3,209 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 2
other RE * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

from sortedcontainers import*
(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)

def Add(i):
  global sl,res
  if s[i]!=i:
    sl.add(s[i])
  else:
    res+=1

def Del(i):
  global sl,res
  if s[i]!=i:
    sl.discard(s[i])
  else:
    res-=1

N=10**6
M=int(N**.5)+1
bucket=[[] for i in range(M)]
ans=[0]*q
for i,(l,r)in enumerate(e):
  if l==1:
    ans[i]=1
  else:
    bucket[(l-1)*M//N]+=(l,r,i),

for i in range(M):
  if i&1:
    bucket[i].sort(key=lambda x:-x[1])
  else:
    bucket[i].sort(key=lambda x:x[1])

sl=SortedList()
res=0
L=R=1

for b in bucket:
  for l,r,i in b:
    while R<r:R+=1;Add(R)
    while L>l:L-=1;Add(L)
    while R>r:Del(R);R-=1
    while L<l:Del(L);L+=1
    # print(l,r,i,sl,sl.bisect_left(l),res)
    ans[i]=sl.bisect_left(l)+res+1
print(*ans,sep='\n')
0