結果

問題 No.3313 Matryoshka
コンテスト
ユーザー sasa8uyauya
提出日時 2025-10-27 15:24:19
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 3,327 ms / 4,000 ms
コード長 634 bytes
コンパイル時間 314 ms
コンパイル使用メモリ 82,740 KB
実行使用メモリ 149,276 KB
最終ジャッジ日時 2025-10-27 15:25:19
合計ジャッジ時間 57,743 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

n=int(input())
p=[tuple(map(int,input().split())) for i in range(n)]
a=0


class FenwickTree:
  def __init__(self,n):
    self.n=n
    self.q=[0]*n
  
  def add(self,p,x):
    p+=1
    while p<=self.n:
      self.q[p-1]+=x
      p+=p&(-p)
  
  def sum(self,l,r):
    return self._sum(r)-self._sum(l)
  
  def _sum(self,r):
    a=0
    while r>0:
      a+=self.q[r-1]
      r-=r&(-r)
    return a


L=10**6+1
st=FenwickTree(L)
for l,r in p:
  a+=st.sum(0,l)
  st.add(l,1)
st=FenwickTree(L)
for l,r in p:
  a+=st.sum(r,L)
  st.add(r,1)
p.sort()
st=FenwickTree(L)
for l,r in p:
  a+=st.sum(r,L)
  st.add(r,1)
a-=n*(n-1)//2
a//=2
print(a)
0