結果

問題 No.2336 Do you like typical problems?
ユーザー とりゐとりゐ
提出日時 2023-06-02 21:55:54
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,433 ms / 2,000 ms
コード長 3,300 bytes
コンパイル時間 406 ms
コンパイル使用メモリ 86,988 KB
実行使用メモリ 203,828 KB
最終ジャッジ日時 2023-08-28 03:21:35
合計ジャッジ時間 12,025 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 72 ms
71,312 KB
testcase_01 AC 73 ms
71,104 KB
testcase_02 AC 73 ms
70,976 KB
testcase_03 AC 73 ms
71,180 KB
testcase_04 AC 73 ms
70,984 KB
testcase_05 AC 73 ms
71,108 KB
testcase_06 AC 73 ms
71,392 KB
testcase_07 AC 73 ms
71,116 KB
testcase_08 AC 153 ms
79,180 KB
testcase_09 AC 146 ms
79,312 KB
testcase_10 AC 153 ms
79,352 KB
testcase_11 AC 154 ms
79,176 KB
testcase_12 AC 152 ms
79,368 KB
testcase_13 AC 1,433 ms
203,828 KB
testcase_14 AC 1,418 ms
203,576 KB
testcase_15 AC 1,401 ms
203,668 KB
testcase_16 AC 1,404 ms
203,464 KB
testcase_17 AC 1,387 ms
203,656 KB
testcase_18 AC 385 ms
93,728 KB
testcase_19 AC 421 ms
95,172 KB
testcase_20 AC 835 ms
185,580 KB
権限があれば一括ダウンロードができます

ソースコード

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)
0