結果

問題 No.2359 A in S ?
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:51:26
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,158 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 153 ms
コンパイル使用メモリ 82,840 KB
実行使用メモリ 125,708 KB
最終ジャッジ日時 2025-03-20 20:51:40
合計ジャッジ時間 6,400 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 2 WA * 1 TLE * 1 -- * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import bisect
from collections import defaultdict

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0

    N = int(input[idx]); idx += 1
    M = int(input[idx]); idx += 1

    T = 300  # Threshold for small X

    # For small X (X <= T), group by (X, Y) and store merged intervals
    small = defaultdict(list)
    large = []  # list of (X, Y, L, R)

    for _ in range(N):
        L = int(input[idx]); idx += 1
        R = int(input[idx]); idx += 1
        X = int(input[idx]); idx += 1
        Y = int(input[idx]); idx += 1

        Y = Y % X  # Ensure Y is within [0, X-1]

        if X <= T:
            start = ((L - Y + X - 1) // X) * X + Y
            if start < L:
                start += X
            end = ((R - Y) // X) * X + Y
            if start > R:
                continue
            # Store the interval [start, end]
            small[(X, Y)].append((start, end))
        else:
            large.append((X, Y, L, R))

    # Preprocess small X groups by merging intervals and sorting
    small_merged = defaultdict(list)
    for key in small:
        intervals = small[key]
        # Sort by start and merge overlapping intervals
        intervals.sort()
        merged = []
        for s, e in intervals:
            if not merged:
                merged.append((s, e))
            else:
                last_s, last_e = merged[-1]
                if s <= last_e + 1:
                    # Merge them
                    new_s = min(s, last_s)
                    new_e = max(e, last_e)
                    merged[-1] = (new_s, new_e)
                else:
                    merged.append((s, e))
        # For merged intervals, sort and also collect prefix max R
        merged.sort()
        starts = []
        ends = []
        max_ends = []
        current_max = -1
        for s, e in merged:
            starts.append(s)
            ends.append(e)
            current_max = max(current_max, e)
            max_ends.append(current_max)
        small_merged[key] = (starts, ends, max_ends)

    # Preprocess the queries
    A_list = list(map(int, input[idx:idx+M]))
    idx += M

    for A in A_list:
        res = 0

        # Check small X
        for X in range(1, T + 1):
            Y = A % X
            key = (X, Y)
            if key not in small_merged:
                continue
            starts, ends, max_ends = small_merged[key]
            # Binary search for the largest start <= A
            pos = bisect.bisect_right(starts, A) - 1
            if pos >= 0:
                # Check if A <= ends[pos]
                if A <= ends[pos]:
                    # Now, need to check if there's any merged interval that covers A
                    # The max_end up to pos is the maximum possible end
                    # Since merged intervals are sorted and non-overlapping, and max_ends is non-decreasing
                    # So if max_ends[pos] >= A, then there is coverage
                    res += 1

        # Check large X
        for (X, Y, L, R) in large:
            if A % X == Y and L <= A <= R:
                res += 1

        print(res)

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