結果

問題 No.2359 A in S ?
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:48:33
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,306 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 144 ms
コンパイル使用メモリ 82,768 KB
実行使用メモリ 235,116 KB
最終ジャッジ日時 2025-03-31 17:49:50
合計ジャッジ時間 8,724 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 6 TLE * 1 -- * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import bisect
from collections import defaultdict

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

    group_map = defaultdict(lambda: {'Ls': [], 'Rs': []})

    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
        group = (X, Y)
        group_map[group]['Ls'].append(L)
        group_map[group]['Rs'].append(R)

    for key in group_map:
        group_map[key]['Ls'].sort()
        group_map[key]['Rs'].sort()

    a_to_groups = defaultdict(list)
    MAX_A = 10**5
    for (X, Y) in group_map:
        a = Y
        while a <= MAX_A:
            if a >= 1:
                a_to_groups[a].append((X, Y))
            a += X

    queries = list(map(int, input[ptr:ptr + m]))
    for a in queries:
        total = 0
        for (X, Y) in a_to_groups.get(a, []):
            entry = group_map[(X, Y)]
            Ls = entry['Ls']
            Rs = entry['Rs']
            cnt_L = bisect.bisect_right(Ls, a)
            cnt_R = bisect.bisect_right(Rs, a - 1)
            total += (cnt_L - cnt_R)
        print(total)

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