結果

問題 No.3207 Digital Font
コンテスト
ユーザー amesyu
提出日時 2025-07-22 17:57:16
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,473 bytes
コンパイル時間 822 ms
コンパイル使用メモリ 82,604 KB
実行使用メモリ 177,132 KB
最終ジャッジ日時 2025-07-22 17:58:16
合計ジャッジ時間 58,886 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 25 WA * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

# Generated By Gemini 2.5 Pro

import sys
from bisect import bisect_left, bisect_right

# Fast input
readline = sys.stdin.readline

class FenwickTree:
    """1D Fenwick Tree (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):
        """Calculates the sum of [0, i-1]"""
        s = 0
        while i > 0:
            s = (s + self.data[i]) % self.mod
            i -= i & -i
        return s

    def query_range(self, l, r):
        """Calculates the sum of [l, r]"""
        if l > r:
            return 0
        res = (self._query(r + 1) - self._query(l) + self.mod) % self.mod
        return res

def solve():
    try:
        H_str, W_str = readline().split()
        H, W = int(H_str), int(W_str)
        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)]
    except (IOError, ValueError):
        return

    # --- Coordinate Compression ---
    # Collect all unique column coordinates from points and query boundaries
    cols_set = set()
    for _, c, _ in points:
        cols_set.add(c)
    for _, d, _, u in queries:
        cols_set.add(d)
        cols_set.add(u)
    all_cols = sorted(list(cols_set))
    col_map = {val: i for i, val in enumerate(all_cols)}
    compressed_w = len(all_cols)

    # --- Hash Preparation ---
    MOD = 10**9 + 7
    P1, P2 = 37, 41

    max_pow = 2 * (H + W)
    pow1 = [1] * (max_pow + 1)
    pow2 = [1] * (max_pow + 1)
    inv1 = pow(P1, MOD - 2, MOD)
    inv2 = pow(P2, MOD - 2, MOD)
    inv_pow1 = [1] * (max_pow + 1)
    inv_pow2 = [1] * (max_pow + 1)

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

    R_fwd = {0: 10, 1: 11, 2: 12, 5: 15, 6: 16, 8: 18, 9: 19}
    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()}

    # --- Event Creation ---
    events = []
    # Point Events: (row, type=0, col_idx, hash_fwd, hash_bwd)
    for r, c, x in points:
        comp_c = col_map[c]
        h_fwd = (pow1[r] * pow2[c] * R_fwd[x]) % MOD
        h_bwd = (inv_pow1[r] * inv_pow2[c] * R_bwd[x]) % MOD
        events.append((r, 0, comp_c, h_fwd, h_bwd))

    # Query Events: (row, type=1, query_idx, start_col_idx, end_col_idx, sign)
    ans_fwd = [0] * Q
    ans_bwd = [0] * Q
    for i in range(Q):
        l, d, r, u = queries[i]
        
        # --- THIS IS THE CORRECTED LOGIC ---
        # Find the compressed column index range for [d, u]
        cd = bisect_left(all_cols, d)
        cu = bisect_right(all_cols, u) - 1
        
        # Add event for the top boundary of the rectangle
        events.append((r, 1, i, cd, cu, 1))
        # Add event for the bottom boundary (exclusive)
        events.append((l - 1, 1, i, cd, cu, -1))

    # --- Sweep-line Processing ---
    events.sort()
    
    bit_fwd = FenwickTree(compressed_w, MOD)
    bit_bwd = FenwickTree(compressed_w, MOD)
    
    for event in events:
        if event[1] == 0:  # Point Event
            _, _, c_idx, hf, hb = event
            bit_fwd.add(c_idx, hf)
            bit_bwd.add(c_idx, hb)
        else:  # Query Event
            _, _, q_idx, cd, cu, sign = event
            sum_f = bit_fwd.query_range(cd, cu)
            sum_b = bit_bwd.query_range(cd, cu)
            
            # Apply sign for inclusion-exclusion
            if sign == 1:
                ans_fwd[q_idx] = (ans_fwd[q_idx] + sum_f) % MOD
                ans_bwd[q_idx] = (ans_bwd[q_idx] + sum_b) % MOD
            else:
                ans_fwd[q_idx] = (ans_fwd[q_idx] - sum_f + MOD) % MOD
                ans_bwd[q_idx] = (ans_bwd[q_idx] - sum_b + MOD) % MOD

    # --- Final Judgment ---
    for i in range(Q):
        l, d, r, u = queries[i]
        
        # The backward hash needs to be shifted to the correct position
        factor = (pow1[r + l] * pow2[u + d]) % MOD
        target_bwd = (ans_bwd[i] * factor) % MOD

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

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