結果

問題 No.2359 A in S ?
コンテスト
ユーザー lam6er
提出日時 2025-04-15 21:19:45
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,814 bytes
コンパイル時間 198 ms
コンパイル使用メモリ 81,892 KB
実行使用メモリ 134,000 KB
最終ジャッジ日時 2025-04-15 21:25:40
合計ジャッジ時間 4,228 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 2 TLE * 1 -- * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

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

    S = int(10**5 ** 0.5)  # Threshold for small X

    small_groups = defaultdict(list)
    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 <= S:
            small_groups[(X, Y)].append((L, R))
        else:
            large_intervals.append((L, R, X, Y))

    # Preprocess large intervals
    max_A = 10**5
    frequency = [0] * (max_A + 2)
    for L, R, X, Y in large_intervals:
        if Y > R:
            continue
        # Compute the first valid A_j >= L
        start = Y
        if start < L:
            k = (L - Y + X - 1) // X
            start = Y + k * X
        if start > R:
            continue
        # Compute the last valid A_j <= R
        end = R - ((R - start) % X)
        if end < start:
            continue
        # Generate all valid A_j and update frequency
        a = start
        while a <= end:
            if a > max_A:
                break
            frequency[a] += 1
            a += X

    # Process queries
    queries = list(map(int, input[ptr:ptr+M]))
    ptr += M
    for A in queries:
        count = 0
        # Check small groups
        for X in range(1, S + 1):
            Y_val = A % X
            ranges = small_groups.get((X, Y_val), [])
            for L, R in ranges:
                if L <= A <= R:
                    count += 1
        # Check large intervals
        if A <= max_A:
            count += frequency[A]
        print(count)

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