結果

問題 No.728 ギブ and テイク
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:35:45
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,457 ms / 3,000 ms
コード長 2,171 bytes
コンパイル時間 286 ms
コンパイル使用メモリ 82,256 KB
実行使用メモリ 217,160 KB
最終ジャッジ日時 2025-03-20 20:37:24
合計ジャッジ時間 13,704 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

class BIT:
    def __init__(self, size):
        self.size = size
        self.tree = [0] * (self.size + 2)  # 1-based indexing

    def update(self, index):
        while index <= self.size:
            self.tree[index] += 1
            index += index & -index

    def query(self, index):
        res = 0
        while index > 0:
            res += self.tree[index]
            index -= index & -index
        return res

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    ptr = 0
    N = int(data[ptr])
    ptr +=1
    A = list(map(int, data[ptr:ptr+N]))
    ptr +=N
    L = []
    R = []
    for _ in range(N):
        l = int(data[ptr])
        r = int(data[ptr+1])
        L.append(l)
        R.append(r)
        ptr +=2
    
    # Step 1: Prepare queries
    queries = []
    for i in range(N):
        current_A = A[i]
        R_i = R[i]
        upper = current_A + R_i
        k = bisect.bisect_right(A, upper) -1
        if k > i:  # j has to be >i and <=k
            queries.append( (current_A, i+1, k) )  # (x, left (0-based), right (0-based))
    
    # Step 2: Sort queries by x (A[i])
    queries.sort()
    
    # Step 3: Prepare sorted_bs (B[j] = A[j] - L[j], sorted by B[j])
    sorted_bs = []
    for j in range(N):
        b = A[j] - L[j]
        sorted_bs.append( (b, j) )  # j is 0-based
    
    # Sort sorted_bs by B[j] ascending, then j ascending
    sorted_bs.sort()
    
    # Step 4: Process queries using BIT
    bit = BIT(N)
    ans = 0
    p = 0  # pointer for sorted_bs
    for x, left_0, right_0 in queries:
        # Add all j where B[j] <=x
        while p < len(sorted_bs) and sorted_bs[p][0] <=x:
            j_0based = sorted_bs[p][1]
            bit.update(j_0based +1)  # convert to 1-based index
            p +=1
        # Calculate the count in [left_0, right_0]
        left = left_0  # 0-based
        right = right_0  # 0-based
        # Query 1-based indices
        # range [left+1, right+1] in BIT
        if left > right:
            continue
        count = bit.query(right +1) - bit.query(left)
        ans += count
    print(ans)

if __name__ == "__main__":
    main()
0