結果

問題 No.3207 Digital Font
ユーザー amesyu
提出日時 2025-07-22 17:54:16
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,738 bytes
コンパイル時間 401 ms
コンパイル使用メモリ 82,124 KB
実行使用メモリ 173,548 KB
最終ジャッジ日時 2025-07-22 17:55:02
合計ジャッジ時間 43,595 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 25 WA * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

# Generated By Gemini 2.5 Pro

import sys

# 高速な入力
readline = sys.stdin.readline

class FenwickTree:
    """1次元Fenwickツリー（BIT）"""
    def __init__(self, n, mod):
        self.n = n
        self.mod = mod
        self.data = [0] * (n + 1)

    def add(self, i, x):
        i += 1
        while i <= self.n:
            self.data[i] = (self.data[i] + x) % self.mod
            i += i & -i

    def query(self, i):
        """[0, i]の和を求める"""
        i += 1
        s = 0
        while i > 0:
            s = (s + self.data[i]) % self.mod
            s %= self.mod
            i -= i & -i
        return s
    
    def query_range(self, l, r):
        """[l, r]の和を求める"""
        if l > r: return 0
        return (self.query(r) - self.query(l - 1) + self.mod) % self.mod

def solve():
    H, W = map(int, readline().split())
    N = int(readline())
    points = [list(map(int, readline().split())) for _ in range(N)]
    Q = int(readline())
    queries = [list(map(int, readline().split())) for _ in range(Q)]

    # --- 座標圧縮 ---
    all_cols = sorted(list(set([p[1] for p in points] + [q[1] for q in queries] + [q[3] for q in queries])))
    col_map = {val: i for i, val in enumerate(all_cols)}
    compressed_w = len(all_cols)

    # --- ハッシュの準備 ---
    MOD1 = 10**9 + 7
    P1, P2 = 37, 41
    
    max_pow = (H + W) * 2
    pow1 = [1] * (max_pow + 1)
    pow2 = [1] * (max_pow + 1)
    inv1 = pow(P1, MOD1 - 2, MOD1)
    inv2 = pow(P2, MOD1 - 2, MOD1)
    inv_pow1 = [1] * (max_pow + 1)
    inv_pow2 = [1] * (max_pow + 1)

    for i in range(max_pow):
        pow1[i+1] = (pow1[i] * P1) % MOD1
        pow2[i+1] = (pow2[i] * P2) % MOD1
        inv_pow1[i+1] = (inv_pow1[i] * inv1) % MOD1
        inv_pow2[i+1] = (inv_pow2[i] * inv2) % MOD1

    R_fwd = {0:123, 1:234, 2:345, 5:456, 6:567, 8:678, 9:789}
    f = {0:0, 1:1, 2:2, 5:5, 6:9, 8:8, 9:6}
    R_bwd = {k: R_fwd[v] for k, v in f.items()}

    # --- イベントの作成 ---
    events = []
    # 点イベント
    for r, c, x in points:
        h_fwd = (pow1[r] * pow2[c] * R_fwd[x]) % MOD1
        h_bwd = (inv_pow1[r] * inv_pow2[c] * R_bwd[x]) % MOD1
        events.append((r, 0, col_map[c], h_fwd, h_bwd))

    # クエリイベント
    ans_fwd = [0] * Q
    ans_bwd = [0] * Q
    for i in range(Q):
        l, d, r, u = queries[i]
        comp_d = col_map.get(d)
        if comp_d is None: comp_d = len(all_cols)
        else: comp_d = col_map[d]

        comp_u = col_map.get(u)
        if comp_u is None: comp_u = -1
        else: comp_u = col_map[u]
        
        # r行目でのクエリ
        events.append((r, 1, i, comp_d, comp_u, 1))
        # l-1行目でのクエリ
        events.append((l - 1, 1, i, comp_d, comp_u, -1))

    # --- 平面走査 ---
    events.sort()
    
    bit_fwd = FenwickTree(compressed_w, MOD1)
    bit_bwd = FenwickTree(compressed_w, MOD1)
    
    for event in events:
        if event[1] == 0:  # 点イベント
            _, _, c, hf, hb = event
            bit_fwd.add(c, hf)
            bit_bwd.add(c, hb)
        else:  # クエリイベント
            _, _, q_idx, cd, cu, sign = event
            sum_f = bit_fwd.query_range(cd, cu)
            sum_b = bit_bwd.query_range(cd, cu)
            
            ans_fwd[q_idx] = (ans_fwd[q_idx] + sign * sum_f + MOD1) % MOD1
            ans_bwd[q_idx] = (ans_bwd[q_idx] + sign * sum_b + MOD1) % MOD1

    # --- 最終判定 ---
    for i in range(Q):
        l, d, r, u = queries[i]
        
        factor = (pow1[r + l] * pow2[u + d]) % MOD1
        target_bwd = (ans_bwd[i] * factor) % MOD1

        if ans_fwd[i] == target_bwd:
            print("Yes")
        else:
            print("No")

solve()
0