結果

問題 No.2359 A in S ?
ユーザー gew1fw
提出日時 2025-06-12 20:20:10
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,055 bytes
コンパイル時間 186 ms
コンパイル使用メモリ 82,732 KB
実行使用メモリ 138,684 KB
最終ジャッジ日時 2025-06-12 20:20:30
合計ジャッジ時間 4,356 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 2 TLE * 1 -- * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

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

    small_X = 300  # threshold for small X
    small_groups = {}  # key: (X, Y), value: list of (L, R) sorted by L
    large_intervals = []

    for _ in range(N):
        L = int(input[ptr])
        ptr += 1
        R = int(input[ptr])
        ptr += 1
        X = int(input[ptr])
        ptr += 1
        Y = int(input[ptr])
        ptr += 1

        if X <= small_X:
            key = (X, Y)
            if key not in small_groups:
                small_groups[key] = []
            small_groups[key].append((L, R))
        else:
            large_intervals.append((X, Y, L, R))

    # Preprocess small groups: sort each group's intervals by L, and prepare for binary search
    for key in small_groups:
        intervals = small_groups[key]
        # Sort intervals by L
        intervals.sort()
        # Replace the group with the sorted list
        small_groups[key] = intervals

    # Read the queries
    queries = list(map(int, input[ptr:ptr+M]))
    ptr += M

    for A in queries:
        ans = 0

        # Process small X groups
        for X in range(1, small_X + 1):
            Y = A % X
            key = (X, Y)
            if key not in small_groups:
                continue
            intervals = small_groups[key]
            # Binary search to find the number of intervals with L <= A
            # Since intervals are sorted by L, we can use bisect_right
            L_list = [interval[0] for interval in intervals]
            k = bisect.bisect_right(L_list, A)
            # Check the first k intervals
            count = 0
            for i in range(k):
                if intervals[i][1] >= A:
                    count += 1
            ans += count

        # Process large X intervals
        for (X, Y, L, R) in large_intervals:
            if A % X == Y and L <= A <= R:
                ans += 1

        print(ans)

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