#1152815 (PyPy3) No.2974 関数の芽

• 問題: No.2974 関数の芽
• ユーザー: LyricalMaestro
• 提出日時: 2026-03-19 02:17:24
• 言語: PyPy3 (7.3.17)
• 結果: TLE
• 実行時間: -
• コード長: 3,852 bytes
• コンパイル時間: 252 ms
• コンパイル使用メモリ: 85,472 KB
• 実行使用メモリ: 241,176 KB
• 最終ジャッジ日時: 2026-03-19 02:17:47
• 合計ジャッジ時間: 20,136 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_1

ファイルパターン	結果
other	AC * 19 TLE * 5

ソースコード

## https://yukicoder.me/problems/no/2974

from functools import cmp_to_key

MIN_X = - 10 ** 10
MAX_X = 10 ** 10

def compare(a, b):
    #数値を昇順ソート
    if a[0] * b[1] > a[1] * b[0]:
        return 1
    elif a[0] * b[1] < a[1] * b[0]:
        return -1
    else:
        return 0


def calc_gcd(A, B):
    """
    正の整数A, Bの最大公約数を計算する
    """
    a = max(A, B)
    b = min(A, B)
    while a % b > 0:
        c = a % b
        a = b
        b = c
    return b

class BinaryIndexTree:
    """
    フェニック木(BinaryIndexTree)の基本的な機能を実装したクラス
    """
    def __init__(self, size):
        self.size = size
        self.array = [[0, 0] for _ in range(size + 1)]
    
    def add(self, x, a):
        index = x
        while index <= self.size:
            self.array[index][0] += a[0]
            self.array[index][1] += a[1]
            index += index & (-index)
    
    def sum(self, x):
        index = x
        ans = [0, 0]
        while index > 0:
            ans[0] += self.array[index][0]
            ans[1] += self.array[index][1]
            index -= index & (-index)
        return ans

    def least_upper_bound(self, value):
        if self.sum(self.size) < value:
            return -1
        elif value <= 0:
            return 0

        m = 1
        while m < self.size:
            m *= 2

        k = 0
        k_sum = 0
        while m > 0:
            k0 = k + m
            if k0 < self.size:
                if k_sum + self.array[k0] < value:
                    k_sum += self.array[k0]
                    k += m
            m //= 2
        if k < self.size:
            return k + 1
        else:
            return -1

def calc_(K, L, calc_cache):
    if L == 0:
        return (0, 1)
    else:
        if (K, L ) in calc_cache:
            return calc_cache[(K, L)]

        gcd = calc_gcd(abs(K), abs(L))
        if K < 0:
            K *= -1
            L *= -1
        x = (-1 * (L // gcd) , K // gcd)
        calc_cache[(K, L)] = x
        return x


def main():
    Q = int(input())
    klmlx = []
    for _ in range(Q):
        K, L, M, N, X = map(int, input().split())
        klmlx.append((K, L, M, N, X))
    
    calc_cache = {}

    # Xにおける座標圧縮
    x_set = {(MIN_X, 1), (MAX_X, 1)}
    for K, L, M, N, X in klmlx:
        x_set.add((X, 1))

        if K != 0:
            y = calc_(K, L, calc_cache)
            x_set.add(y)

        if M != 0:
            y = calc_(M, N, calc_cache)
            x_set.add(y)

    x_list = list(x_set)
    x_list = sorted(x_list, key=cmp_to_key(compare))
    x_map = {}
    for i , a in enumerate(x_list):
        x_map[a] = i + 1

    # 本編を解く
    bit = BinaryIndexTree(len(x_map))

    for k, l, m, n, x in klmlx:
        if k == 0:
            if l > 0:
                bit.add(1, (0, l))
                bit.add(len(x_map), (0, -l))
        elif k > 0:
            f1 = calc_(k, l, calc_cache)
            bit.add(x_map[f1], (k, l))
            bit.add(len(x_map), (-k, -l))
        else:
            f1 = calc_(k, l, calc_cache)
            bit.add(1, (k, l))
            bit.add(x_map[f1], (-k, -l))

        if m == 0:
            if n > 0:
                bit.add(1, (0, -n))
                bit.add(len(x_map), (0, n))
        elif m > 0:
            f1 = calc_(m, n, calc_cache)
            bit.add(x_map[f1], (-m, -n))
            bit.add(len(x_map), (m, n))
        else:
            f1 = calc_(m, n, calc_cache)
            bit.add(1, (-m, -n))
            bit.add(x_map[f1], (m, n))

        x_ = x_map[(x, 1)]

        y1 = bit.sum(x_ - 1)
        y2 = bit.sum(x_)

        if y1[0] == 0 and y1[1] == 0 and y2[0] == 0 and y2[1] == 0:
            print("Yes")
        else:
            print("No")

    

                




if __name__ == "__main__":
    main()