結果

問題 No.3313 Matryoshka
コンテスト
ユーザー kidodesu
提出日時 2025-10-24 22:50:56
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,302 bytes
コンパイル時間 485 ms
コンパイル使用メモリ 82,704 KB
実行使用メモリ 265,504 KB
最終ジャッジ日時 2025-10-24 22:52:05
合計ジャッジ時間 64,131 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33 TLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

class BIT:
    # 長さN+1の配列を初期化
    def __init__(self, N):
        self.size = N
        self.bit = [0]*(N+1)

    # i番目までの和を求める
    def sum(self, i):
        res = 0
        while i > 0:
            res += self.bit[i] # フェニック木のi番目の値を加算
            i -= -i & i # 最も右にある1の桁を0にする
        return res

    # i番目の値にxを足して更新する
    def add(self, i, x):
        while i <= self.size:
            self.bit[i] += x # フェニック木のi番目にxを足して更新
            i += -i & i # 最も右にある1の桁に1を足す


n = int(input())
ans = 0
LR = [list(map(int, input().split())) for _ in range(n)]
A = []
for l, r in LR:
    A.append(l)
    A.append(r)
A.sort()
I = {A[i]: i for i in range(2*n)}
for i in range(n):
    LR[i][0] = I[LR[i][0]]
    LR[i][1] = I[LR[i][1]]
st = BIT(2*n)
ans0 = 0
inf = 1 << 30
cnt = 0
for l, r in LR[::-1]:
    #print(st.sum(2*n), st.sum(r), st.sum(l))
    t0 = st.sum(l) % inf
    t1 = (st.sum(2*n) - st.sum(r)) // inf
    #print(t0, t1, cnt)
    ans0 += t0 + t1 - cnt
    st.add(l+1, 1)
    st.add(r+1, inf)
    cnt += 1
st = BIT(2*n)
LR.sort(reverse = True)
ans1 = 0
for l, r in LR:
    ans1 += st.sum(r)
    st.add(r, 1)

print((ans1 - ans0) // 2)
0