結果

問題 No.3207 Digital Font
コンテスト
ユーザー ゼット
提出日時 2025-07-18 22:52:50
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 3,183 bytes
コンパイル時間 450 ms
コンパイル使用メモリ 82,316 KB
実行使用メモリ 848,368 KB
最終ジャッジ日時 2025-07-18 22:52:54
合計ジャッジ時間 3,414 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 MLE * 1
other -- * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

mod=998244353
H,W=map(int,input().split())
pa=100
pb=201
zz=200
z=zz
M=(H+z+1)//z
N=int(input())
h=[[0]*(W+1) for i in range(M)]
h2=[[0]*(W+1) for i in range(M)]
L=[[] for i in range(H)]
A=[[] for i in range(H)]
B=[[] for i in range(H)]
L2=[[] for i in range(H)]
A2=[[] for i in range(H)]
B2=[[] for i in range(H)]
u=[i for i in range(10)]
u2=u[:]
u2[9]=6
u2[6]=9
for i in range(N):
    a,b,x=map(int,input().split())
    a-=1
    b-=1
    pos=a//z
    score=u[x]
    score*=pow(pa,a,mod)
    score%=mod
    score*=pow(pb,b,mod)
    score%=mod
    h[pos][b]+=score
    L[a].append((b,score))
    a,b=H-1-a,W-1-b
    pos=a//z
    score=u2[x]
    score*=pow(pa,a,mod)
    score%=mod
    score*=pow(pb,b,mod)
    score%=mod
    h2[pos][b]+=score
    L2[a].append((b,score))
for i in range(M):
    for j in range(1,W):
        h[i][j]+=h[i][j-1]
        h[i][j]%=mod
for i in range(H):
    e=L[i][:]
    e.sort()
    for C in e:
        b,x=C[:]
        A[i].append(b)
        B[i].append(x)
    for j in range(1,len(B[i])):
        B[i][j]+=B[i][j-1]
for i in range(M):
    for j in range(1,W):
        h2[i][j]+=h2[i][j-1]
        h2[i][j]%=mod
for i in range(H):
    e=L2[i][:]
    e.sort()
    for C in e:
        b,x=C[:]
        A2[i].append(b)
        B2[i].append(x)
    for j in range(1,len(B2[i])):
        B2[i][j]+=B2[i][j-1]
from bisect import bisect_right
Q=int(input())
for _ in range(Q):
    l,p,r,q=map(int,input().split())
    l-=1
    r-=1
    p-=1
    q-=1
    w=0
    t=l//z
    pos=l%z
    for i in range(pos,z):
        x=z*t+i
        if x>=H:
            break
        k=bisect_right(A[x],q)
        if k>0:
            w+=B[x][k-1]
            w%=mod
        k=bisect_right(A[x],p-1)
        if k>0:
            w-=B[x][k-1]
            w%=mod
    t=r//z
    pos=r%z
    for i in range(pos+1):
        x=z*t+i
        k=bisect_right(A[x],q)
        if k>0:
            w+=B[x][k-1]
            w%=mod
        k=bisect_right(A[x],p-1)
        if k>0:
            w-=B[x][k-1]
            w%=mod
    st=l//z
    go=r//z
    for i in range(st+1,go):
        w+=h[i][q]-h[i][p-1]
        w%=mod
    if (l//z)==(r//z):
        t=l//z
        w-=h[t][q]-h[t][p-1]
        w%=mod
    w*=pow(pa,-l,mod)
    w%=mod
    w*=pow(pb,-p,mod)
    w%=mod
    l,r=H-1-r,H-1-l
    p,q=W-1-q,W-1-p
    w2=0
    t=l//z
    pos=l%z
    for i in range(pos,z):
        x=z*t+i
        if x>=H:
            break
        k=bisect_right(A2[x],q)
        if k>0:
            w2+=B2[x][k-1]
            w2%=mod
        k=bisect_right(A2[x],p-1)
        if k>0:
            w2-=B2[x][k-1]
            w2%=mod
    t=r//z
    pos=r%z
    for i in range(pos+1):
        x=z*t+i
        k=bisect_right(A2[x],q)
        if k>0:
            w2+=B2[x][k-1]
            w2%=mod
        k=bisect_right(A2[x],p-1)
        if k>0:
            w2-=B2[x][k-1]
            w2%=mod
    st=l//z
    go=r//z
    for i in range(st+1,go):
        w2+=h2[i][q]-h2[i][p-1]
        w2%=mod
    if (l//z)==(r//z):
        t=l//z
        w2-=h2[t][q]-h2[t][p-1]
        w2%=mod
    w2*=pow(pa,-l,mod)
    w2%=mod
    w2*=pow(pb,-p,mod)
    w2%=mod
    if w==w2:
        print('Yes')
    else:
        print('No')
0