結果

問題 No.3101 Range Eratosthenes Query
ユーザー moon17
提出日時 2025-04-11 22:34:41
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,597 bytes
コンパイル時間 475 ms
コンパイル使用メモリ 82,324 KB
実行使用メモリ 116,956 KB
最終ジャッジ日時 2025-04-11 22:34:51
合計ジャッジ時間 9,803 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 6 TLE * 1 -- * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

(q,),*e=[[*map(int,s.split())]for s in open(0)]
class segtree():
 n,size,log,d,op,e=1,1,2,[0],None,10**15
 def __init__(self,V,OP,E):
  self.n=len(V);self.op=OP;self.e=E
  self.log=(self.n-1).bit_length()
  self.size=1<<self.log
  self.d=[E for i in range(2*self.size)]
  for i in range(self.n):self.d[self.size+i]=V[i]
  for i in range(self.size-1,0,-1):self.update(i)
 def set(self,p,x):
  assert 0<=p and p<self.n
  p+=self.size;self.d[p]=x
  for i in range(1,self.log+1):self.update(p>>i)
 def get(self,p):
  assert 0<=p and p<self.n
  return self.d[p+self.size]
 def prod(self,l,r):
  assert 0<=l and l<=r and r<=self.n
  sml,smr=self.e,self.e
  l+=self.size;r+=self.size
  while l<r:
   if l&1:sml=self.op(sml,self.d[l]);l+=1
   if r&1:smr=self.op(self.d[r-1],smr);r-=1
   l>>=1
   r>>=1
  return self.op(sml,smr)
 def all_prod(self):
  return self.d[1]
 def max_right(self,l,f):
  assert 0<=l and l<=self.n
  assert f(self.e)
  if l==self.n:return self.n
  l+=self.size;sm=self.e
  while 1:
   while l%2==0:l>>=1
   if not(f(self.op(sm,self.d[l]))):
    while(l<self.size):
     l=2*l
     if f(self.op(sm,self.d[l])):sm=self.op(sm,self.d[l]);l+=1
    return l-self.size
   sm=self.op(sm,self.d[l]);l+=1
   if (l&-l)==l:break
  return self.n
 def min_left(self,r,f):
  assert 0<=r and r<=self.n
  assert f(self.e)
  if r==0:return 0
  r+=self.size;sm=self.e
  while 1:
   r-=1
   while r>1 and r%2:r>>=1
   if not(f(self.op(self.d[r],sm))):
    while r<self.size:
     r=(2*r+1)
     if f(self.op(self.d[r],sm)):sm=self.op(self.d[r],sm);r-=1
    return r+1-self.size
   sm=self.op(self.d[r],sm)
   if (r&-r)==r:break
  return 0
 def update(self,k):
  self.d[k]=self.op(self.d[2*k],self.d[2*k+1])
 def __str__(self):
  return str([self.get(i) for i in range(self.n)])

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.set(s[i],sl.get(s[i])+1)
  else:
    res+=1

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

N=10**6+10
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=segtree([0]*N,lambda x,y:x+y,0)
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
    ans[i]=sl.prod(0,l)+res+1
print(*ans,sep='\n')
0