結果

問題 No.2359 A in S ?
ユーザー lam6er
提出日時 2025-04-16 15:30:57
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 3,785 bytes
コンパイル時間 147 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 849,208 KB
最終ジャッジ日時 2025-04-16 15:34:47
合計ジャッジ時間 3,070 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 2 MLE * 1 -- * 15
権限があれば一括ダウンロードができます

ソースコード

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

    intervals = []
    max_A = 0
    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
        intervals.append((L, R, X, Y))

    A_list = list(map(int, input[ptr:ptr+M]))
    ptr += M
    max_A = max(A_list) if M > 0 else 0

    # Small X processing (X <= 316)
    SMALL_LIMIT = 316
    small = defaultdict(lambda: defaultdict(list))  # small[X][Y] = list of (L, R) sorted by L

    for L, R, X, Y in intervals:
        if X <= SMALL_LIMIT:
            small[X][Y].append((L, R))

    # For each (X, Y) in small, sort by L and preprocess R's into a sorted list for binary search
    # We'll use a list of sorted R's for each (X, Y)
    # Additionally, for each (X, Y), we'll have a list of R's sorted in ascending order for each prefix
    # To handle this, we'll precompute for each (X, Y) group:
    # - sorted_LR: list of (L, R) sorted by L
    # - sorted_R_prefix: list of sorted R's up to each index
    small_preprocessed = defaultdict(lambda: defaultdict(dict))

    for X in small:
        for Y in small[X]:
            sorted_LR = sorted(small[X][Y], key=lambda x: x[0])
            Ls = [x[0] for x in sorted_LR]
            Rs = [x[1] for x in sorted_LR]
            # Precompute sorted R's for each prefix
            sorted_R_prefix = []
            current_Rs = []
            for r in Rs:
                bisect.insort(current_Rs, r)
                sorted_R_prefix.append(current_Rs.copy())
            small_preprocessed[X][Y] = {
                'Ls': Ls,
                'Rs': Rs,
                'sorted_R_prefix': sorted_R_prefix
            }

    # Large X processing (X > 316)
    frequency = [0] * (10**5 + 2)  # since A_j can be up to 1e5

    for L, R, X, Y in intervals:
        if X > SMALL_LIMIT:
            # Compute first and last valid A
            if Y > R:
                continue
            # Compute first valid A >= L and A ≡ Y mod X
            if L <= Y <= R:
                first = Y
            else:
                # Compute the smallest k such that Y + k*X >= L
                k = (L - Y + X - 1) // X
                first = Y + k * X
                if first < L:
                    first += X
            if first > R:
                continue
            # Compute last valid A <= R
            last = Y + ((R - Y) // X) * X
            if last < first:
                continue
            # Generate all A in [first, last] step X
            current = first
            while current <= last:
                if 1 <= current <= 10**5:
                    frequency[current] += 1
                current += X

    # Process queries
    for A in A_list:
        res = frequency[A]
        # Check small X groups
        for X in small_preprocessed:
            Y_val = A % X
            if Y_val not in small_preprocessed[X]:
                continue
            group = small_preprocessed[X][Y_val]
            Ls = group['Ls']
            # Find the number of intervals with L <= A
            k = bisect.bisect_right(Ls, A)
            if k == 0:
                continue
            # Now, among the first k intervals, count how many have R >= A
            # Use the precomputed sorted_R_prefix for k-1 (0-based)
            sorted_Rs = group['sorted_R_prefix'][k-1]
            # Find the first index in sorted_Rs >= A
            cnt = len(sorted_Rs) - bisect.bisect_left(sorted_Rs, A)
            res += cnt
        print(res)

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