結果

問題 No.2327 Inversion Sum
ユーザー とりゐとりゐ
提出日時 2023-05-28 14:03:56
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 398 ms / 2,000 ms
コード長 2,926 bytes
コンパイル時間 1,314 ms
コンパイル使用メモリ 86,912 KB
実行使用メモリ 85,768 KB
最終ジャッジ日時 2023-08-27 08:56:22
合計ジャッジ時間 7,827 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 181 ms
85,524 KB
testcase_01 AC 365 ms
85,768 KB
testcase_02 AC 304 ms
85,568 KB
testcase_03 AC 178 ms
84,988 KB
testcase_04 AC 396 ms
85,628 KB
testcase_05 AC 188 ms
81,576 KB
testcase_06 AC 313 ms
84,900 KB
testcase_07 AC 261 ms
82,832 KB
testcase_08 AC 198 ms
80,824 KB
testcase_09 AC 375 ms
85,140 KB
testcase_10 AC 224 ms
82,516 KB
testcase_11 AC 93 ms
79,924 KB
testcase_12 AC 92 ms
79,668 KB
testcase_13 AC 89 ms
77,032 KB
testcase_14 AC 298 ms
81,788 KB
testcase_15 AC 398 ms
84,924 KB
testcase_16 AC 238 ms
84,772 KB
testcase_17 AC 152 ms
81,704 KB
testcase_18 AC 196 ms
81,052 KB
testcase_19 AC 218 ms
85,120 KB
testcase_20 AC 77 ms
71,268 KB
testcase_21 AC 76 ms
71,360 KB
testcase_22 AC 77 ms
71,176 KB
testcase_23 AC 76 ms
71,508 KB
testcase_24 AC 76 ms
71,284 KB
testcase_25 AC 75 ms
71,304 KB
testcase_26 AC 77 ms
71,440 KB
testcase_27 AC 76 ms
71,516 KB
testcase_28 AC 76 ms
71,184 KB
testcase_29 AC 75 ms
71,300 KB
testcase_30 AC 78 ms
71,316 KB
testcase_31 AC 77 ms
71,176 KB
testcase_32 AC 78 ms
71,412 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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



n,m=map(int,input().split())
mst=[-1]*n
use=[1]*n
for _ in range(m):
  p,k=map(int,input().split())
  mst[k-1]=p-1
  use[p-1]=0

free=[0]*n
for i in range(n):
  if i>=1:
    free[i]=free[i-1]
  if mst[i]==-1:
    free[i]+=1

mod=998244353
rem=segtree(use,lambda x,y:x+y,0)
seg=segtree([0]*n,lambda x,y:x+y,0)
ans1=0
ans2=0
for i in range(n):
  if mst[i]!=-1:
    ans1+=seg.query(mst[i],n)
    seg.update(mst[i],1)
    L=rem.query(0,mst[i])
    R=rem.query(mst[i],n)
    ans2+=free[i]*(R)%mod*pow(L+R,mod-2,mod)%mod
    ans2+=(L+R-free[i])*L%mod*pow(L+R,mod-2,mod)%mod
    ans2%=mod

ans3=free[-1]*(free[-1]-1)%mod*pow(4,mod-2,mod)%mod

ans=ans1+ans2+ans3
ans%=mod
for i in range(1,free[-1]+1):
  ans*=i
  ans%=mod

print(ans)
0