結果

問題 No.3207 Digital Font
ユーザー amesyu
提出日時 2025-07-15 19:21:53
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,989 ms / 3,000 ms
コード長 4,366 bytes
コンパイル時間 166 ms
コンパイル使用メモリ 82,360 KB
実行使用メモリ 167,044 KB
最終ジャッジ日時 2025-07-16 21:18:22
合計ジャッジ時間 73,160 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

class SegmentTree:
    def __init__(self, arr, op, e):
        self.op = op
        self.e = e
        self.n = len(arr)
        self.log = (self.n - 1).bit_length()
        self.size = 1 << self.log
        self.tree = [self.e for _ in range(2 * self.size)]
        for i in range(self.n): self.tree[i + self.size] = arr[i]
        for i in range(self.size - 1, 0, -1): self.update(i)
    def update(self, i):
        self.tree[i] = self.op(self.tree[2 * i + 0], self.tree[2 * i + 1])
    def set(self, i, x):
        i += self.size
        self.tree[i] = x
        i >>= 1
        while i:
            self.update(i)
            i >>= 1
    def get(self, i):
        return self.tree[i + self.size]
    def prod(self, l, r):
        pl = self.e
        pr = self.e
        l += self.size
        r += self.size
        while l < r:
            if l & 1:
                pl = self.op(pl, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                pr = self.op(self.tree[r], pr)
            l >>= 1
            r >>= 1
        return self.op(pl, pr)
    def all_prod(self):
        return self.tree[1]
    def max_right(self, l, func):
        assert(func(self.e))
        if l == self.n: return self.n
        l += self.size
        sm = self.e
        while True:
            while l & 1 == 0: l >>= 1
            if not func(self.op(sm, self.tree[l])):
                while l < self.size:
                    l = 2 * l
                    if func(self.op(sm, self.tree[l])):
                        sm = self.op(sm, self.tree[l])
                        l += 1
                return l - self.size
            sm = self.op(sm, self.tree[l])
            l += 1
            if (l & -l) == l: break
        return self.n
    def min_left(self, r, func):
        assert(func(self.e))
        if r == 0: return 0;
        r += self.size
        sm = self.e
        while True:
            r -= 1
            while r > 1 and r & 1: r >>= 1
            if not func(self.op(self.tree[r], sm)):
                while r < self.size:
                    r = 2 * r + 1
                    if func(self.op(self.tree[r], sm)):
                        sm = self.op(self.tree[r], sm)
                        r -= 1
                return r + 1 - self.size
            sm = self.op(self.tree[r], sm)
            if (r & -r) == r: break
        return 0
    def __str__(self):
        return f"SegmentTree{[self.get(i) for i in range(self.n)]}"
    __repr__ = __str__

MOD = (1 << 61) - 1
def op(x, y):
    return (x + y) % MOD
e = 0

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()
    
    seg = SegmentTree([0] * W, op, e)
    ans = [0] * Q
    
    j = 0
    for x, i in qs:
        l, d, r, u = query[i % Q]
        while j < N and add[j][0] < x:
            idx = add[j][1]
            seg.set(idx, (seg.get(idx) + add[j][2]) % MOD)
            j += 1
        if i < Q:
            ans[i] -= seg.prod(d, u)
            ans[i] %= MOD
        else:
            ans[i % Q] += seg.prod(d, u)
            ans[i % Q] %= MOD
    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 = []
query1 = []
add2 = []
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], ans2[i]
    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