結果

問題 No.2336 Do you like typical problems?
ユーザー とりゐ
提出日時 2023-06-02 21:55:54
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,523 ms / 2,000 ms
コード長 3,300 bytes
コンパイル時間 445 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 200,576 KB
最終ジャッジ日時 2024-12-28 17:34:57
合計ジャッジ時間 12,056 ms
ジャッジサーバーID
(参考情報)
judge4 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

from sys import stdin
input=lambda :stdin.readline()[:-1]
class segtree():
def __init__(self,init,func,ide):
self.n=len(init)
self.func=func
self.ide=ide
self.size=1<<(self.n-1).bit_length()
self.tree=[self.ide for i in range(2*self.size)]
for i in range(self.n):
self.tree[self.size+i]=init[i]
for i in range(self.size-1,0,-1):
self.tree[i]=self.func(self.tree[2*i], self.tree[2*i|1])
def update(self,k,x):
k+=self.size
self.tree[k]=x
k>>=1
while k:
self.tree[k]=self.func(self.tree[2*k],self.tree[k*2|1])
k>>=1
def get(self,i):
return self.tree[i+self.size]
def query(self,l,r):
l+=self.size
r+=self.size
l_res=self.ide
r_res=self.ide
while l<r:
if l&1:
l_res=self.func(l_res,self.tree[l])
l+=1
if r&1:
r-=1
r_res=self.func(self.tree[r],r_res)
l>>=1
r>>=1
return self.func(l_res,r_res)
def max_right(self,l,f):
assert 0<=l<=self.n
assert f(self.ide)
if l==self.n:
return self.n
l+=self.size
res=self.ide
while True:
while l&1==0:
l>>=1
if not f(self.func(res,self.tree[l])):
while l<self.size:
l*=2
if f(self.func(res,self.tree[l])):
res=self.func(res,self.tree[l])
l+=1
return l-self.size
res=self.func(res,self.tree[l])
l+=1
if l&(-l)==l:
break
return self.n
def min_left(self,r,f):
assert 0<=r<=self.n
assert f(self.ide)
if r==0:
return 0
r+=self.size
res=self.ide
while True:
r-=1
while r>1 and r&1:
r>>=1
if not f(self.func(self.tree[r],res)):
while r<self.size:
r=2*r+1
if f(self.func(self.tree[r],res)):
res=self.func(self.tree[r],res)
r-=1
return r+1-self.size
res=self.func(self.tree[r],res)
if r&(-r)==r:
break
return 0
def __getitem__(self,i):
return self.get(i)
def __setitem__(self,key,val):
self.update(key,val)
def __iter__(self):
for i in range(self.n):
yield self.tree[i+self.size]
def __str__(self):
return str(list(self))
mod=998244353
n=int(input())
invs=[]
bc=[]
s=set()
for i in range(n):
b,c=map(int,input().split())
s.add(b)
#s.add(b+1)
#s.add(c)
s.add(c+1)
bc.append((b,c))
invs.append(pow(c-b+1,mod-2,mod))
s=sorted(list(s))
m=len(s)
d={}
for i in range(m):
d[s[i]]=i
C=[0]*(m-1)
for i in range(m-1):
C[i]=s[i+1]-s[i]
cum=[0]*(m+1)
for i in range(n):
b,c=bc[i]
cum[d[b]]+=invs[i]
cum[d[c+1]]-=invs[i]
for i in range(1,m+1):
cum[i]+=cum[i-1]
seg=segtree([cum[i]*C[i] for i in range(m-1)],lambda x,y:x+y,0)
ans=0
def modint_to_frac(a,mod):
a%=mod
if a==0:
return '0/1'
for X in range(1,10000):
Y=a*X%mod
if 0<Y<10000:
return str(Y)+'/'+str(X)
if mod-10000<Y<mod:
return '-'+str(mod-Y)+'/'+str(X)
return 'inexpressible'
for i in range(n):
b,c=bc[i]
res=seg.query(d[b],d[c+1])-1
ans+=res*invs[i]
ans%=mod
ans*=pow(2,mod-2,mod)
ans%=mod
ans=n*(n-1)//2-ans
ans%=mod
for i in range(1,n+1):
ans*=i
ans%=mod
ans*=pow(2,mod-2,mod)
ans%=mod
#print(modint_to_frac(ans,mod))
print(ans)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0