結果

問題 No.3313 Matryoshka
コンテスト
ユーザー kidodesu
提出日時 2025-10-24 22:37:20
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,120 bytes
コンパイル時間 476 ms
コンパイル使用メモリ 82,636 KB
実行使用メモリ 266,004 KB
最終ジャッジ日時 2025-10-24 22:37:52
合計ジャッジ時間 28,049 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 WA * 30
権限があれば一括ダウンロードができます

ソースコード

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)
ans = 0
inf = 1 << 30
for l, r in LR[::-1]:
    t0 = (st.sum(r) - st.sum(l)) % inf
    t1 = (st.sum(2*n-1) - st.sum(r)) // inf
    #print(t0, t1)
    ans += t0 - t1
    st.add(l+1, 1)
    st.add(r+1, inf)
print(ans)
0