結果
問題 | 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 |
ソースコード
from sys import stdininput=lambda :stdin.readline()[:-1]class segtree():def __init__(self,init,func,ide):self.n=len(init)self.func=funcself.ide=ideself.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.sizeself.tree[k]=xk>>=1while k:self.tree[k]=self.func(self.tree[2*k],self.tree[k*2|1])k>>=1def get(self,i):return self.tree[i+self.size]def query(self,l,r):l+=self.sizer+=self.sizel_res=self.ider_res=self.idewhile l<r:if l&1:l_res=self.func(l_res,self.tree[l])l+=1if r&1:r-=1r_res=self.func(self.tree[r],r_res)l>>=1r>>=1return self.func(l_res,r_res)def max_right(self,l,f):assert 0<=l<=self.nassert f(self.ide)if l==self.n:return self.nl+=self.sizeres=self.idewhile True:while l&1==0:l>>=1if not f(self.func(res,self.tree[l])):while l<self.size:l*=2if f(self.func(res,self.tree[l])):res=self.func(res,self.tree[l])l+=1return l-self.sizeres=self.func(res,self.tree[l])l+=1if l&(-l)==l:breakreturn self.ndef min_left(self,r,f):assert 0<=r<=self.nassert f(self.ide)if r==0:return 0r+=self.sizeres=self.idewhile True:r-=1while r>1 and r&1:r>>=1if not f(self.func(self.tree[r],res)):while r<self.size:r=2*r+1if f(self.func(self.tree[r],res)):res=self.func(self.tree[r],res)r-=1return r+1-self.sizeres=self.func(self.tree[r],res)if r&(-r)==r:breakreturn 0def __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=998244353n=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]]=iC=[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=0def modint_to_frac(a,mod):a%=modif a==0:return '0/1'for X in range(1,10000):Y=a*X%modif 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])-1ans+=res*invs[i]ans%=modans*=pow(2,mod-2,mod)ans%=modans=n*(n-1)//2-ansans%=modfor i in range(1,n+1):ans*=ians%=modans*=pow(2,mod-2,mod)ans%=mod#print(modint_to_frac(ans,mod))print(ans)