結果
問題 |
No.3207 Digital Font
|
ユーザー |
![]() |
提出日時 | 2025-07-17 16:23:43 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 178 ms / 3,000 ms |
コード長 | 6,298 bytes |
コンパイル時間 | 6,105 ms |
コンパイル使用メモリ | 336,100 KB |
実行使用メモリ | 27,112 KB |
最終ジャッジ日時 | 2025-07-17 16:23:57 |
合計ジャッジ時間 | 12,186 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 38 |
ソースコード
#include <bits/stdc++.h> using namespace std; using std::cerr; using std::cin; using std::cout; #if __has_include(<atcoder/all>) #include <atcoder/all> using mint = atcoder::modint998244353; istream &operator>>(istream &is, mint &a) { long long t; is >> t; a = t; return is; } ostream &operator<<(ostream &os, mint a) { return os << a.val(); } #endif typedef long double ld; #define long long long #define uint unsigned int #define ull unsigned long #define overload3(a, b, c, name, ...) name #define rep3(i, a, b) for (int i = (a); i < (b); i++) #define rep2(i, n) rep3(i, 0, n) #define rep1(n) rep2(__i, n) #define rep(...) overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__) #define per3(i, a, b) for (int i = (b) - 1; i >= (a); i--) #define per2(i, n) per3(i, 0, n) #define per1(n) per2(__i, n) #define per(...) overload3(__VA_ARGS__, per3, per2, per1)(__VA_ARGS__) #define all(a) a.begin(), a.end() #define UNIQUE(a) \ sort(all(a)); \ a.erase(unique(all(a)), a.end()) #define sz(a) (int)a.size() #define vec vector #ifndef DEBUG #define cerr \ if (0) \ cerr // #undef assert // #define assert(...) void(0) #undef endl #define endl '\n' #endif template <typename T> ostream &operator<<(ostream &os, vector<T> a) { const int n = a.size(); rep(i, n) { os << a[i]; if (i + 1 != n) os << " "; } return os; } template <typename T, size_t n> ostream &operator<<(ostream &os, array<T, n> a) { rep(i, n) { os << a[i]; if (i + 1 != n) os << " "; } return os; } template <typename T> istream &operator>>(istream &is, vector<T> &a) { for (T &i : a) is >> i; return is; } template <typename T, typename S> bool chmin(T &x, S y) { if ((T)y < x) { x = (T)y; return true; } return false; } template <typename T, typename S> bool chmax(T &x, S y) { if (x < (T)y) { x = (T)y; return true; } return false; } template <typename T> void operator++(vector<T> &a) { for (T &i : a) ++i; } template <typename T> void operator--(vector<T> &a) { for (T &i : a) --i; } template <typename T> void operator++(vector<T> &a, int) { for (T &i : a) i++; } template <typename T> void operator--(vector<T> &a, int) { for (T &i : a) i--; } struct modint { private: static constexpr long MASK30 = (1UL << 30) - 1; static constexpr long MASK31 = (1UL << 31) - 1; static constexpr long MOD = (1LL << 61) - 1; static constexpr long MASK61 = MOD; static long CalcMod(long x) { long xu = x >> 61; long xd = x & MASK61; long res = xu + xd; if (res >= MOD) res -= MOD; return res; } static long Mul(long a, long b) { long au = a >> 31; long ad = a & MASK31; long bu = b >> 31; long bd = b & MASK31; long mid = ad * bu + au * bd; long midu = mid >> 30; long midd = mid & MASK30; return CalcMod(au * bu * 2 + midu + (midd << 31) + ad * bd); } public: long val; modint(long v) { val = CalcMod(v); }; modint() : modint(0) {} modint &operator++() { if (++val == MOD) val = 0; return *this; } modint &operator--() { if (--val == -1) val = MOD - 1; return *this; } modint &operator+=(const modint &rhs) { val += rhs.val; if (val >= MOD) val -= MOD; return *this; } modint &operator-=(const modint &rhs) { val -= rhs.val; if (val < 0) val += MOD; return *this; } modint &operator*=(const modint &rhs) { val = Mul(val, rhs.val); return *this; } modint pow(long b) const { modint ans = 1, p = *this; while (b) { if (b & 1) ans *= p; p *= p; b >>= 1; } return ans; } friend modint operator++(modint &a, int) { modint res = a; ++a; return res; } friend modint operator--(modint &a, int) { modint res = a; --a; return res; } friend modint operator+(const modint &lhs, const modint &rhs) { return modint(lhs) += rhs; } friend modint operator-(const modint &lhs, const modint &rhs) { return modint(lhs) -= rhs; } friend modint operator*(const modint &lhs, modint rhs) { return modint(lhs) *= rhs; } friend bool operator==(const modint &lhs, const modint &rhs) { return lhs.val == rhs.val; } friend bool operator!=(const modint &lhs, const modint &rhs) { return lhs.val != rhs.val; } friend bool operator<(const modint &lhs, const modint &rhs) { return lhs.val < rhs.val; } friend ostream &operator<<(ostream &os, modint &rhs) { return os << rhs.val; } }; struct S { int j; int idx; int bai; }; void solve() { int h, w, n; cin >> h >> w >> n; constexpr int INF = 2e5 + 1; const modint a = rand(), b = rand(); const modint ainv = a.pow((1LL << 61) - 3), binv = b.pow((1LL << 61) - 3); vec<modint> ap(INF), bp(INF); ap[0] = bp[0] = 1; rep(i, 1, INF) { ap[i] = a * ap[i - 1]; bp[i] = b * bp[i - 1]; } vec<modint> ainvp(INF), binvp(INF); ainvp[0] = binvp[0] = 1; rep(i, 1, INF) { ainvp[i] = ainv * ainvp[i - 1]; binvp[i] = binv * binvp[i - 1]; } vec<vec<pair<int, int>>> g(h + 1); rep(i, n) { int ii, jj, x; cin >> ii >> jj >> x; ii--, jj--; g[ii].emplace_back(jj, x); } int m; cin >> m; vec<modint> av(m), bv(m); vec<int> ax(m), bx(m); vec<vec<S>> gg(h + 1); rep(i, m) { int l1, r1, l2, r2; cin >> l1 >> r1 >> l2 >> r2; l1--, r1--; ax[i] = l1 + l2 - 1, bx[i] = r1 + r2 - 1; gg[l2].emplace_back(r2, i, 1); gg[l1].emplace_back(r2, i, -1); gg[l2].emplace_back(r1, i, -1); gg[l1].emplace_back(r1, i, 1); } auto flip = [](int x) { if (x == 6) return 9; if (x == 9) return 6; return x; }; atcoder::fenwick_tree<modint> fwa(w), fwb(w); rep(i, h + 1) { for (auto [j, idx, bai] : gg[i]) { av[idx] += bai * fwa.sum(0, j); bv[idx] += bai * fwb.sum(0, j); } for (auto [j, x] : g[i]) { fwa.add(j, x * ap[i] * bp[j]); fwb.add(j, flip(x) * ainvp[i] * binvp[j]); } } rep(i, m) { if (bv[i] == av[i] * ainvp[ax[i]] * binvp[bx[i]]) { cout << "Yes" << endl; } else { cout << "No" << endl; } } } int main() { // srand((unsigned)time(NULL)); cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); int t = 1; // cin >> t; while (t--) solve(); }