結果

問題 No.3207 Digital Font
ユーザー amesyu
提出日時 2025-07-16 21:37:28
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,604 ms / 3,000 ms
コード長 2,248 bytes
コンパイル時間 513 ms
コンパイル使用メモリ 82,904 KB
実行使用メモリ 165,712 KB
最終ジャッジ日時 2025-07-16 21:38:35
合計ジャッジ時間 66,354 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

class FenwickTree:
    def __init__(self, n):
        self.size = n
        self.data = [0] * n
    
    def add(self, p, x):
        assert 0 <= p < self.size
        p += 1
        while p <= self.size:
            self.data[p - 1] += x
            p += p & -p

    def get(self, r):
        result = 0
        while r > 0:
            result += self.data[r - 1]
            r -= r & -r
        return result

    def sum(self, l, r):
        assert 0 <= l <= r <= self.size
        return self.get(r) - self.get(l)

MOD = 10 ** 9 + 7

def rectangle_sum(H, W, add, query):

    N = len(add)
    Q = len(query)

    add.sort(key = lambda x: x[1])

    qs = []
    for i in range(Q):
        l, d, r, u = query[i]
        qs.append((l, i))
        qs.append((r, i + Q))

    qs.sort()
    add.sort()
    
    bit = FenwickTree(W)
    ans = [0] * Q
    
    j = 0
    for x, i in qs:
        p = i % Q
        l, d, r, u = query[p]
        while j < N and add[j][0] < x:
            idx = add[j][1]
            bit.add(idx, add[j][2])
            j += 1
        if i < Q: ans[p] -= bit.sum(d, u)
        else: ans[p] += bit.sum(d, u)
    return ans

H, W = map(int, input().split())
N = int(input())

B1, B2 = 10007, 10009
H1, H2 = [1], [1]
for _ in range(H): H1.append((H1[-1] * B1) % MOD)
for _ in range(W): H2.append((H2[-1] * B2) % MOD)

def get_weight(i, j):
    return (H1[i] * H2[j]) % MOD

f = [0, 1, 2, -1, -1, 5, 9, -1, 8, 6]

add1, add2 = [], []
query1, query2 = [], []

for _ in range(N):
    i, j, x = map(int, input().split())
    i -= 1
    j -= 1
    add1.append((        i,         j, (x    * get_weight(        i,         j)) % MOD))
    add2.append((H - i - 1, W - j - 1, (f[x] * get_weight(H - i - 1, W - j - 1)) % MOD))

Q = int(input())
for _ in range(Q):
    l, d, r, u = map(int, input().split())
    l -= 1
    d -= 1
    query1.append((    l,     d,     r,     u))
    query2.append((H - r, W - u, H - l, W - d))

ans1 = rectangle_sum(H, W, add1, query1)
ans2 = rectangle_sum(H, W, add2, query2)

for i in range(Q):
    hash1, hash2 = ans1[i] % MOD, ans2[i] % MOD
    l, d, r, u = query1[i]
    w1 = get_weight(l, d)
    w2 = get_weight(H - r, W - u)
    print("Yes" if (hash1 * w2) % MOD == (hash2 * w1) % MOD else "No")
0