結果

問題 No.3207 Digital Font
コンテスト
ユーザー amesyu
提出日時 2025-07-22 17:52:21
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 4,514 bytes
コンパイル時間 365 ms
コンパイル使用メモリ 82,656 KB
実行使用メモリ 849,524 KB
最終ジャッジ日時 2025-07-22 17:52:29
合計ジャッジ時間 4,462 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other MLE * 1 -- * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

# Generated By Gemini 2.5 Pro

import sys

# 再帰回数の上限を増やす
sys.setrecursionlimit(2 * 10**5 + 5)

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

class FenwickTree2D:
    """2次元Fenwickツリー（BIT）"""
    def __init__(self, h, w):
        self.h = h
        self.w = w
        self.data = [[0] * (w + 1) for _ in range(h + 1)]

    def add(self, r, c, x):
        r += 1
        c += 1
        while r <= self.h:
            nc = c
            while nc <= self.w:
                self.data[r][nc] += x
                nc += nc & -nc
            r += r & -r

    def _query(self, r, c):
        r += 1
        c += 1
        s = 0
        while r > 0:
            nc = c
            while nc > 0:
                s += self.data[r][nc]
                nc -= nc & -nc
            r -= r & -r
        return s

    def query(self, r1, c1, r2, c2):
        """長方形領域 [r1, r2] x [c1, c2] の和を求める"""
        return self._query(r2, c2) - self._query(r1 - 1, c2) - self._query(r2, c1 - 1) + self._query(r1 - 1, c1 - 1)


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_rows = sorted(list(set([p[0] for p in points] + [q[0] for q in queries] + [q[2] for q in queries])))
    all_cols = sorted(list(set([p[1] for p in points] + [q[1] for q in queries] + [q[3] for q in queries])))
    
    row_map = {val: i for i, val in enumerate(all_rows)}
    col_map = {val: i for i, val in enumerate(all_cols)}
    
    compressed_h = len(all_rows)
    compressed_w = len(all_cols)

    # --- ハッシュの準備 ---
    MOD1, MOD2 = 10**9 + 7, 10**9 + 9
    P1, P2 = 37, 41
    
    # P1, P2のべき乗とモジュラ逆数を事前計算
    max_coord = max(H, W) * 2 + 1
    pow1_1 = [1] * (max_coord + 1)
    pow2_1 = [1] * (max_coord + 1)
    inv1_1 = [1] * (max_coord + 1)
    inv2_1 = [1] * (max_coord + 1)
    
    P1_inv1 = pow(P1, MOD1 - 2, MOD1)
    P2_inv1 = pow(P2, MOD1 - 2, MOD1)

    for i in range(max_coord):
        pow1_1[i+1] = (pow1_1[i] * P1) % MOD1
        pow2_1[i+1] = (pow2_1[i] * P2) % MOD1
        inv1_1[i+1] = (inv1_1[i] * P1_inv1) % MOD1
        inv2_1[i+1] = (inv2_1[i] * P2_inv1) % 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()}

    # --- Fenwickツリーの構築 ---
    # 衝突を避けるためハッシュを2セット使う（今回は1セットで実装）
    bit_fwd = FenwickTree2D(compressed_h, compressed_w)
    bit_bwd = FenwickTree2D(compressed_h, compressed_w)

    for r, c, x in points:
        comp_r, comp_c = row_map[r], col_map[c]
        
        h_fwd = (pow1_1[r] * pow2_1[c] * R_fwd[x]) % MOD1
        h_bwd = (inv1_1[r] * inv2_1[c] * R_bwd[x]) % MOD1
        
        bit_fwd.add(comp_r, comp_c, h_fwd)
        bit_bwd.add(comp_r, comp_c, h_bwd)
        
    # --- クエリ処理 ---
    for l, d, r, u in queries:
        # 圧縮後の座標範囲を求める
        comp_l = row_map.get(l)
        if comp_l is None: # もし範囲の端点が非ゼロ要素になければ二分探索で探す
             idx =_bisect_left(all_rows, l)
             comp_l = idx
        
        comp_r = row_map.get(r)
        if comp_r is None:
             idx = _bisect_right(all_rows, r)
             comp_r = idx - 1
        
        comp_d = col_map.get(d)
        if comp_d is None:
             idx =_bisect_left(all_cols, d)
             comp_d = idx
        
        comp_u = col_map.get(u)
        if comp_u is None:
            idx = _bisect_right(all_cols, u)
            comp_u = idx - 1

        if comp_l > comp_r or comp_d > comp_u:
            # 範囲内に非ゼロ要素が一つも無い
            print("Yes")
            continue

        sum_fwd = bit_fwd.query(comp_l, comp_d, comp_r, comp_u) % MOD1
        
        sum_bwd_base = bit_bwd.query(comp_l, comp_d, comp_r, comp_u) % MOD1
        
        factor = (pow1_1[r + l] * pow2_1[u + d]) % MOD1
        sum_bwd = (sum_bwd_base * factor) % MOD1
        
        if sum_fwd == sum_bwd:
            print("Yes")
        else:
            print("No")

from bisect import bisect_left as _bisect_left, bisect_right as _bisect_right
solve()
0