結果

問題 No.3207 Digital Font
コンテスト
ユーザー ゼット
提出日時 2025-07-18 23:08:45
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 8,087 bytes
コンパイル時間 4,610 ms
コンパイル使用メモリ 307,956 KB
実行使用メモリ 353,136 KB
最終ジャッジ日時 2025-07-18 23:08:56
合計ジャッジ時間 10,262 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 1
other TLE * 1 -- * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

/*
mod=998244353
H,W=map(int,input().split())
pa=100
pb=201
zz=500
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')

*/

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int mod = 998244353;
const int pa = 100;
const int pb = 201;
const int zz = 500;
const int z = zz;

ll mod_pow(ll x, ll n, ll m) {
    ll res = 1;
    x %= m;
    if (n < 0) {
        x = mod_pow(x, m - 2, m);  // Modular inverse
        n = -n;
    }
    while (n > 0) {
        if (n & 1) res = res * x % m;
        x = x * x % m;
        n >>= 1;
    }
    return res;
}

int main() {
    int H, W;
    cin >> H >> W;
    int M = (H + z + 1) / z;
    int N;
    cin >> N;

    vector<vector<ll>> h(M, vector<ll>(W + 1));
    vector<vector<ll>> h2(M, vector<ll>(W + 1));
    vector<vector<pair<int, ll>>> L(H), L2(H);
    vector<vector<int>> A(H), A2(H);
    vector<vector<ll>> B(H), B2(H);
    vector<int> u(10), u2(10);
    iota(u.begin(), u.end(), 0);
    u2 = u;
    u2[9] = 6;
    u2[6] = 9;

    for (int i = 0; i < N; ++i) {
        int a, b, x;
        cin >> a >> b >> x;
        a--; b--;
        int pos = a / z;
        ll score = u[x];
        score = score * mod_pow(pa, a, mod) % mod;
        score = score * mod_pow(pb, b, mod) % mod;
        h[pos][b+1] = (h[pos][b+1] + score) % mod;
        L[a].emplace_back(b, score);

        a = H - 1 - a;
        b = W - 1 - b;
        pos = a / z;
        score = u2[x];
        score = score * mod_pow(pa, a, mod) % mod;
        score = score * mod_pow(pb, b, mod) % mod;
        h2[pos][b+1] = (h2[pos][b+1] + score) % mod;
        L2[a].emplace_back(b, score);
    }

    for (int i = 0; i < M; ++i)
        for (int j = 1; j < W+1; ++j)
            h[i][j] = (h[i][j] + h[i][j - 1]) % mod;

    for (int i = 0; i < H; ++i) {
        sort(L[i].begin(), L[i].end());
        for (auto& [b, x] : L[i]) {
            A[i].push_back(b);
            B[i].push_back(x);
        }
        for (int j = 1; j < B[i].size(); ++j)
            B[i][j] = (B[i][j] + B[i][j - 1]) % mod;
    }

    for (int i = 0; i < M; ++i)
        for (int j = 1; j < W+1; ++j)
            h2[i][j] = (h2[i][j] + h2[i][j - 1]) % mod;

    for (int i = 0; i < H; ++i) {
        sort(L2[i].begin(), L2[i].end());
        for (auto& [b, x] : L2[i]) {
            A2[i].push_back(b);
            B2[i].push_back(x);
        }
        for (int j = 1; j < B2[i].size(); ++j)
            B2[i][j] = (B2[i][j] + B2[i][j - 1]) % mod;
    }

    int Q;
    cin >> Q;
    while (Q--) {
        int l, p, r, q;
        cin >> l >> p >> r >> q;
        l--; p--; r--; q--;
        ll w = 0;

        int st = l / z, go = r / z;

        for (int i = l % z; st * z + i <= r && i < z; ++i) {
            int x = st * z + i;
            if (x >= H) break;
            int k = upper_bound(A[x].begin(), A[x].end(), q) - A[x].begin();
            if (k > 0) w = (w + B[x][k - 1]) % mod;
            k = upper_bound(A[x].begin(), A[x].end(), p - 1) - A[x].begin();
            if (k > 0) w = (w - B[x][k - 1] + mod) % mod;
        }
        for (int i = 0; go * z + i <= r && i < z; ++i) {
            int x = go * z + i;
            int k = upper_bound(A[x].begin(), A[x].end(), q) - A[x].begin();
            if (k > 0) w = (w + B[x][k - 1]) % mod;
            k = upper_bound(A[x].begin(), A[x].end(), p - 1) - A[x].begin();
            if (k > 0) w = (w - B[x][k - 1] + mod) % mod;
        }
        for (int i = st + 1; i < go; ++i) {
            w = (w + h[i][q+1] - h[i][p] + mod) % mod;
            
        }
        if (st == go)
            w = (w - h[st][q+1] + h[st][p] + mod) % mod;
        w = w * mod_pow(pa, -l, mod) % mod;
        w = w * mod_pow(pb, -p, mod) % mod;

        int l2 = H - 1 - r, r2 = H - 1 - l;
        int p2 = W - 1 - q, q2 = W - 1 - p;
        ll w2 = 0;
        st = l2 / z;
        go = r2 / z;

        for (int i = l2 % z; st * z + i <= r2 && i < z; ++i) {
            int x = st * z + i;
            if (x >= H) break;
            int k = upper_bound(A2[x].begin(), A2[x].end(), q2) - A2[x].begin();
            if (k > 0) w2 = (w2 + B2[x][k - 1]) % mod;
            k = upper_bound(A2[x].begin(), A2[x].end(), p2 - 1) - A2[x].begin();
            if (k > 0) w2 = (w2 - B2[x][k - 1] + mod) % mod;
        }

        for (int i = 0; go * z + i <= r2 && i < z; ++i) {
            int x = go * z + i;
            int k = upper_bound(A2[x].begin(), A2[x].end(), q2) - A2[x].begin();
            if (k > 0) w2 = (w2 + B2[x][k - 1]) % mod;
            k = upper_bound(A2[x].begin(), A2[x].end(), p2 - 1) - A2[x].begin();
            if (k > 0) w2 = (w2 - B2[x][k - 1] + mod) % mod;
        }

        for (int i = st + 1; i < go; ++i) {
            w2 = (w2 + h2[i][q2+1] - h2[i][p2] + mod) % mod;
        }

        if (st == go)
            w2 = (w2 - h2[st][q2+1] + h2[st][p2] + mod) % mod;

        w2 = w2 * mod_pow(pa, -l2, mod) % mod;
        w2 = w2 * mod_pow(pb, -p2, mod) % mod;

        cout << (w == w2 ? "Yes" : "No") << '\n';
    }
    

    return 0;
}
0