結果

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

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N, M = int(data[idx]), int(data[idx+1])
    idx +=2
    
    intervals = defaultdict(list)
    for _ in range(N):
        L = int(data[idx])
        R = int(data[idx+1])
        X = int(data[idx+2])
        Y = int(data[idx+3])
        idx +=4
        
        # Compute a_i and b_i
        numerator = L - Y
        if numerator <= 0:
            a_i = Y
        else:
            k = (numerator + X -1) // X
            a_i = Y + k * X
        if a_i > R:
            continue
        
        numerator = R - Y
        k = numerator // X
        b_i = Y + k * X
        
        # Add the interval [a_i, b_i]
        intervals[(X, Y)].append((a_i, b_i))
    
    # For each (X,Y), sort the intervals by a_i
    for key in intervals:
        intervals[key].sort(key=lambda x: x[0])
    
    # Read A_j's
    A = list(map(int, data[idx:idx+M]))
    idx += M
    
    # For each query, process
    distinct_X = set()
    for key in intervals:
        X = key[0]
        distinct_X.add(X)
    distinct_X = sorted(distinct_X)
    
    for a in A:
        count =0
        for X in distinct_X:
            Y = a % X
            key = (X, Y)
            if key not in intervals:
                continue
            lst = intervals[key]
            left = 0
            right = len(lst)
            # Find the first interval where a_i <= a and b_i >=a
            # Since intervals are sorted by a_i, we can use binary search
            # to find the first a_i <= a, and then check if b_i >=a
            # But since the list may have many intervals, we can count how many intervals satisfy a_i <= a <= b_i
            # We can perform binary search to find the rightmost a_i <= a, and then check if b_i >=a
            # But this is O(1) per interval, which is not feasible.
            # Instead, for each interval in lst, check if a is within [a_i, b_i]
            # But this is O(K) per query, which is too slow.
            # To optimize, we can pre-process each (X,Y) to have a list of a_i and b_i, and then for a given a, count how many a_i <= a <= b_i
            # To do this, we can precompute a prefix sum array for each (X,Y) that allows us to quickly compute the count.
            # However, this is not feasible due to memory constraints.
            # Therefore, we have to accept that this approach is too slow and find an alternative.
            # For the purpose of this solution, we will proceed with this approach, but it may not pass the time constraints.
            for (ai, bi) in lst:
                if ai <= a <= bi:
                    count +=1
        print(count)
    
if __name__ == '__main__':
    main()
0