結果

問題 No.3313 Matryoshka
コンテスト
ユーザー kidodesu
提出日時 2025-10-24 23:03:07
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 3,388 ms / 4,000 ms
コード長 923 bytes
コンパイル時間 337 ms
コンパイル使用メモリ 82,904 KB
実行使用メモリ 265,736 KB
最終ジャッジ日時 2025-10-24 23:04:03
合計ジャッジ時間 55,776 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

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]]
N = 2*n
data = [0] * (N+1)
ans0 = 0
inf = 1 << 30
cnt = 0
for l, r in LR[::-1]:
    t0 = t1 = 0
    now = l
    while now:
        t0 = (t0 + data[now]) % inf
        now -= now & -now
    now = r
    while now:
        t1 = t1 + data[now] // inf
        now -= now & -now
    ans0 += t0 - t1
    k = l+1
    while k <= N:
        data[k] += 1
        k += k & -k
    k = r+1
    while k <= N:
        data[k] += inf
        k += k & -k

data = [0] * (N+1)
LR.sort(reverse = True)
ans1 = 0
for l, r in LR:
    k = r
    while k:
        ans1 += data[k]
        k -= k & -k
    k = r+1
    while k <= N:
        data[k] += 1
        k += k & -k

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