結果

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

ソースコード

diff #

import bisect
from collections import defaultdict

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N, M = int(input[ptr]), int(input[ptr+1])
    ptr +=2
    
    x_to_ys = defaultdict(set)
    groups = defaultdict(lambda: {'L': [], 'R': []})
    
    for _ in range(N):
        L = int(input[ptr])
        R = int(input[ptr+1])
        X = int(input[ptr+2])
        Y = int(input[ptr+3])
        ptr +=4
        
        x_to_ys[X].add(Y)
        groups[(X, Y)]['L'].append(L)
        groups[(X, Y)]['R'].append(R)
    
    # Sort L and R for each group
    for key in groups:
        groups[key]['L'].sort()
        groups[key]['R'].sort()
    
    # Precompute unique Xs
    unique_Xs = list(x_to_ys.keys())
    
    # Process queries
    queries = list(map(int, input[ptr:ptr+M]))
    ptr += M
    
    for A in queries:
        count = 0
        for X in unique_Xs:
            Y = A % X
            if Y not in x_to_ys[X]:
                continue
            group = groups.get((X, Y), None)
            if not group:
                continue
            L_list = group['L']
            R_list = group['R']
            cnt_L = bisect.bisect_right(L_list, A)
            cnt_R = bisect.bisect_left(R_list, A)
            count += (cnt_L - cnt_R)
        print(count)

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