結果

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

ソースコード

diff # 

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

    max_A = 10**5
    sqrt_max = int(max_A**0.5)  # Approximately 317

    # Category a: X <= sqrt_max
    category_a = defaultdict(list)
    # Category b: X > sqrt_max
    category_b = defaultdict(list)

    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 <= sqrt_max:
            key = (X, Y)
            category_a[key].append((L, R))
        else:
            current = Y
            while current <= max_A:
                category_b[current].append((L, R))
                current += X

    # Process category_a into events and prefix sums
    processed_a = {}
    for key in category_a:
        X, Y = key
        intervals = category_a[key]
        events = []
        for L, R in intervals:
            events.append((L, 1))
            events.append((R + 1, -1))
        events.sort()
        positions = []
        prefix = []
        current_pos = None
        current_sum = 0
        for pos, delta in events:
            if pos != current_pos:
                if current_pos is not None:
                    positions.append(current_pos)
                    prefix.append(current_sum)
                current_pos = pos
            current_sum += delta
        if current_pos is not None:
            positions.append(current_pos)
            prefix.append(current_sum)
        positions.append(max_A + 1)
        prefix.append(0)
        processed_a[key] = (positions, prefix)

    # Process queries
    queries = list(map(int, input[ptr:ptr + M]))
    ptr += M
    for A in queries:
        count_a = 0
        for X in range(1, sqrt_max + 1):
            Y = A % X
            key = (X, Y)
            if key not in processed_a:
                continue
            positions, prefix = processed_a[key]
            idx = bisect.bisect_right(positions, A) - 1
            if idx >= 0:
                count_a += prefix[idx]

        count_b = 0
        if A in category_b:
            for L, R in category_b[A]:
                if L <= A <= R:
                    count_b += 1

        print(count_a + count_b)

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