結果

問題 No.647 明太子
ユーザー lam6er
提出日時 2025-03-20 20:32:03
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 144 ms / 4,500 ms
コード長 2,825 bytes
コンパイル時間 167 ms
コンパイル使用メモリ 82,336 KB
実行使用メモリ 82,668 KB
最終ジャッジ日時 2025-03-20 20:33:01
合計ジャッジ時間 3,048 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    n = int(input[ptr])
    ptr +=1

    members = []
    for _ in range(n):
        a = int(input[ptr])
        b = int(input[ptr+1])
        members.append((a, b))
        ptr +=2

    # Sort members by A_j ascending, then B_j ascending
    members.sort(key=lambda x: (x[0], x[1]))
    sorted_A = [x[0] for x in members]
    sorted_B = [x[1] for x in members]

    m = int(input[ptr])
    ptr +=1
    mentaiko_list = []
    for _ in range(m):
        x = int(input[ptr])
        y = int(input[ptr+1])
        mentaiko_list.append((x, y))
        ptr +=2

    class SegmentTree:
        def __init__(self, data):
            self.n = len(data)
            self.size = 1
            while self.size < self.n:
                self.size <<= 1
            self.tree = [[] for _ in range(2 * self.size)]
            for i in range(self.n):
                self.tree[self.size + i] = [data[i]]
            for i in range(self.size - 1, 0, -1):
                left = self.tree[2 * i]
                right = self.tree[2 * i + 1]
                merged = []
                l_ptr = r_ptr = 0
                while l_ptr < len(left) and r_ptr < len(right):
                    if left[l_ptr] <= right[r_ptr]:
                        merged.append(left[l_ptr])
                        l_ptr +=1
                    else:
                        merged.append(right[r_ptr])
                        r_ptr +=1
                merged.extend(left[l_ptr:])
                merged.extend(right[r_ptr:])
                self.tree[i] = merged

        def query(self, l, r, y):
            res = 0
            l += self.size
            r += self.size
            while l < r:
                if l % 2 == 1:
                    res += bisect.bisect_right(self.tree[l], y)
                    l +=1
                if r % 2 == 1:
                    r -=1
                    res += bisect.bisect_right(self.tree[r], y)
                l >>=1
                r >>=1
            return res

    if not sorted_B:
        st = None
    else:
        st = SegmentTree(sorted_B)

    max_count = 0
    counts = []
    for idx, (x, y) in enumerate(mentaiko_list):
        low = bisect.bisect_left(sorted_A, x)
        if low >= len(sorted_A):
            cnt = 0
        else:
            if st is None:
                cnt =0
            else:
                cnt = st.query(low, len(sorted_A), y)
        counts.append((cnt, idx +1))
        if cnt > max_count:
            max_count = cnt

    result = []
    for cnt, num in counts:
        if cnt == max_count and cnt >0:
            result.append(num)
    result.sort()
    if len(result) ==0:
        print(0)
    else:
        print('\n'.join(map(str, result)))

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