結果

問題 No.3207 Digital Font
ユーザー amesyu
提出日時 2025-07-22 18:03:35
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,159 ms / 3,000 ms
コード長 5,113 bytes
コンパイル時間 2,434 ms
コンパイル使用メモリ 82,348 KB
実行使用メモリ 190,036 KB
最終ジャッジ日時 2025-07-22 18:04:44
合計ジャッジ時間 55,820 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

# Generated By Gemini 2.5 Pro

import sys
from bisect import bisect_left, bisect_right
import random

def solve():
    """
    Solves the point-symmetric matrix problem using an offline sweep-line
    algorithm with double hashing, correctly handling the value 0.
    """
    try:
        # Fast I/O
        readline = sys.stdin.readline
        H_str, W_str = readline().split()
        H, W = int(H_str), int(W_str)
        N = int(readline())
        points = [tuple(map(int, readline().split())) for _ in range(N)]
        Q = int(readline())
        queries = [tuple(map(int, readline().split())) for _ in range(Q)]
    except (IOError, ValueError):
        return

    # --- 1. Hashing and Coordinate Compression Setup ---

    MOD1, MOD2 = 10**9 + 7, 998244353
    P1_1, P2_1 = 37, 41
    P1_2, P2_2 = 43, 47

    max_pow_dim1 = 2 * H + 2
    max_pow_dim2 = 2 * W + 2

    def precompute_powers(p, mod, size):
        p_inv = pow(p, mod - 2, mod)
        pows = [1] * size
        inv_pows = [1] * size
        for i in range(1, size):
            pows[i] = (pows[i - 1] * p) % mod
            inv_pows[i] = (inv_pows[i - 1] * p_inv) % mod
        return pows, inv_pows

    pow1_1, inv_pow1_1 = precompute_powers(P1_1, MOD1, max_pow_dim1)
    pow2_1, inv_pow2_1 = precompute_powers(P2_1, MOD1, max_pow_dim2)
    pow1_2, inv_pow1_2 = precompute_powers(P1_2, MOD2, max_pow_dim1)
    pow2_2, inv_pow2_2 = precompute_powers(P2_2, MOD2, max_pow_dim2)

    # --- THE CRITICAL FIX IS HERE ---
    rng = random.Random(42)
    R = {x: rng.randint(1, MOD1 - 1) for x in [1, 2, 5, 6, 8, 9]}
    R[0] = 0  # A value of 0 must have a hash contribution of 0.
    
    f = {0: 0, 1: 1, 2: 2, 5: 5, 6: 9, 8: 8, 9: 6}
    R_f = {k: R[v] for k, v in f.items()}

    # Coordinate compression for columns
    cols_set = set(p[1] for p in points)
    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)}
    
    # --- 2. Event Creation for Sweep-line ---
    events = []
    # Point events
    for r, c, x in points:
        if x == 0: continue # Explicit 0s have 0 hash, so we can skip them
        comp_c = col_map[c]
        h1_fwd = (pow1_1[r] * pow2_1[c] * R[x]) % MOD1
        h1_bwd = (inv_pow1_1[r] * inv_pow2_1[c] * R_f[x]) % MOD1
        h2_fwd = (pow1_2[r] * pow2_2[c] * R[x]) % MOD2
        h2_bwd = (inv_pow1_2[r] * inv_pow2_2[c] * R_f[x]) % MOD2
        events.append((r, 0, comp_c, h1_fwd, h1_bwd, h2_fwd, h2_bwd))

    # Query events
    ans = [[0, 0, 0, 0] for _ in range(Q)]
    for i in range(Q):
        l, d, r, u = queries[i]
        cd = bisect_left(all_cols, d)
        cu = bisect_right(all_cols, u) - 1
        if cd <= cu:
            events.append((r, 1, i, cd, cu, 1))
            if l > 1:
                events.append((l - 1, 1, i, cd, cu, -1))
    
    events.sort()

    # --- 3. Sweep-line Processing ---
    bit1_fwd, bit1_bwd = FenwickTree(len(all_cols), MOD1), FenwickTree(len(all_cols), MOD1)
    bit2_fwd, bit2_bwd = FenwickTree(len(all_cols), MOD2), FenwickTree(len(all_cols), MOD2)
    
    for event in events:
        type = event[1]
        if type == 0:  # Point Event
            _, _, c_idx, h1f, h1b, h2f, h2b = event
            bit1_fwd.add(c_idx, h1f)
            bit1_bwd.add(c_idx, h1b)
            bit2_fwd.add(c_idx, h2f)
            bit2_bwd.add(c_idx, h2b)
        else:  # Query Event
            _, _, q_idx, cd, cu, sign = event
            s1f, s1b = bit1_fwd.query_range(cd, cu), bit1_bwd.query_range(cd, cu)
            s2f, s2b = bit2_fwd.query_range(cd, cu), bit2_bwd.query_range(cd, cu)
            
            # Apply sign for inclusion-exclusion
            ans[q_idx][0] = (ans[q_idx][0] + sign * s1f) % MOD1
            ans[q_idx][1] = (ans[q_idx][1] + sign * s1b) % MOD1
            ans[q_idx][2] = (ans[q_idx][2] + sign * s2f) % MOD2
            ans[q_idx][3] = (ans[q_idx][3] + sign * s2b) % MOD2

    # --- 4. Final Judgment ---
    for i in range(Q):
        l, d, r, u = queries[i]
        
        factor1 = (pow1_1[r + l] * pow2_1[u + d]) % MOD1
        target1_bwd = (ans[i][1] * factor1) % MOD1
        check1 = (ans[i][0] == target1_bwd)
        
        factor2 = (pow1_2[r + l] * pow2_2[u + d]) % MOD2
        target2_bwd = (ans[i][3] * factor2) % MOD2
        check2 = (ans[i][2] == target2_bwd)

        if check1 and check2:
            print("Yes")
        else:
            print("No")

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):
        s = 0
        while i > 0:
            s = (s + self.data[i]) % self.mod
            i -= i & -i
        return s

    def query_range(self, l, r):
        if l > r: return 0
        return (self._query(r + 1) - self._query(l) + self.mod) % self.mod

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