結果

問題 No.3207 Digital Font
コンテスト
ユーザー amesyu
提出日時 2025-07-22 18:01:47
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 5,335 bytes
コンパイル時間 494 ms
コンパイル使用メモリ 82,220 KB
実行使用メモリ 192,412 KB
最終ジャッジ日時 2025-07-22 18:02:46
合計ジャッジ時間 56,658 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 25 WA * 13
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# 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 to check for symmetry.
    """
    try:
        # Fast I/O
        readline = sys.stdin.readline
        H, W = map(int, readline().split())
        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 ---

    # Use two independent sets of constants for double hashing
    MOD1, P1_1, P2_1 = 10**9 + 7, 37, 41
    MOD2, P1_2, P2_2 = 998244353, 43, 47

    # Pre-compute powers of P and their modular inverses
    max_pow_dim1 = 2 * H + 1
    max_pow_dim2 = 2 * W + 1

    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)

    # Assign random hash values to digits
    rng = random.Random(42)
    f = {0: 0, 1: 1, 2: 2, 5: 5, 6: 9, 8: 8, 9: 6}
    R = {x: rng.randint(1, MOD1 - 1) for x in range(10)}
    R_f = {k: R[v] for k, v in f.items()}

    # Coordinate compression for columns
    all_cols = sorted(list(set(p[1] for p in points) | set(q[1] for q in queries) | set(q[3] for q in queries)))
    col_map = {val: i for i, val in enumerate(all_cols)}
    
    # --- 2. Event Creation for Sweep-line ---
    events = []
    # Point events: (row, type=0, col_idx, hashes...)
    for r, c, x in points:
        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: (row, type=1, query_idx, start_col_idx, end_col_idx, sign)
    ans = [[0, 0, 0, 0] for _ in range(Q)] # fwd1, bwd1, fwd2, bwd2
    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 = FenwickTree(len(all_cols), MOD1)
    bit1_bwd = FenwickTree(len(all_cols), MOD1)
    bit2_fwd = FenwickTree(len(all_cols), MOD2)
    bit2_bwd = 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)
            
            term1f = (sign * s1f + MOD1) % MOD1
            term1b = (sign * s1b + MOD1) % MOD1
            term2f = (sign * s2f + MOD2) % MOD2
            term2b = (sign * s2b + MOD2) % MOD2

            ans[q_idx][0] = (ans[q_idx][0] + term1f) % MOD1
            ans[q_idx][1] = (ans[q_idx][1] + term1b) % MOD1
            ans[q_idx][2] = (ans[q_idx][2] + term2f) % MOD2
            ans[q_idx][3] = (ans[q_idx][3] + term2b) % MOD2

    # --- 4. Final Judgment ---
    for i in range(Q):
        l, d, r, u = queries[i]
        
        # Check first hash
        factor1 = (pow1_1[r + l] * pow2_1[u + d]) % MOD1
        target1_bwd = (ans[i][1] * factor1) % MOD1
        check1 = (ans[i][0] == target1_bwd)
        
        # Check second hash
        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) - defined inside solve for encapsulation"""
    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