結果

問題 No.3207 Digital Font
コンテスト
ユーザー Kude
提出日時 2025-07-19 00:32:08
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 343 ms / 3,000 ms
コード長 5,311 bytes
コンパイル時間 4,264 ms
コンパイル使用メモリ 330,884 KB
実行使用メモリ 19,332 KB
最終ジャッジ日時 2025-07-19 00:32:24
合計ジャッジ時間 14,186 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
namespace {
#pragma GCC diagnostic ignored "-Wunused-function"
#include<atcoder/all>
#pragma GCC diagnostic warning "-Wunused-function"
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }
template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; }
using ll = long long;
using P = pair<int,int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;

class mint61 {
  using ull = unsigned long long;
  using ui128 = __uint128_t;

 public:
  static constexpr unsigned long long mod = (1ULL << 61) - 1;
  ull v = 0;
  constexpr mint61() {}
  explicit constexpr mint61(ull x) {
    v = (x >> 61) + (x & mod);
    if (v >= mod) v -= mod;
  }
  static constexpr mint61 raw(ull x) {
    mint61 res;
    res.v = x;
    return res;
  }
  friend constexpr mint61 operator+(mint61 lhs, mint61 rhs) {
    auto res = lhs.v + rhs.v;
    return raw(res < mod ? res : res - mod);
  }
  friend constexpr mint61 operator-(mint61 lhs, mint61 rhs) {
    return raw(lhs.v >= rhs.v ? lhs.v - rhs.v : mod + lhs.v - rhs.v);
  }
  static constexpr ull multiply_loose_mod(mint61 lhs, mint61 rhs) {
    // ab = q(m+1)+r = qm+q+r
    // q+r = ab-qm = ab-floor(ab/(m+1))m < ab-(ab/(m+1)-1)m = ab/(m+1)+m <=
    // (m-1)^2/(m+1)+m = 2m-3+4/(m+1)
    auto mul = ui128(lhs.v) * rhs.v;
    return ull(mul >> 61) + ull(mul & mod);
  }
  friend constexpr mint61 operator*(mint61 lhs, mint61 rhs) {
    auto res = multiply_loose_mod(lhs, rhs);
    return raw(res < mod ? res : res - mod);
  }
  mint61& operator+=(mint61 rhs) { return *this = *this + rhs; }
  mint61& operator-=(mint61 rhs) { return *this = *this - rhs; }
  mint61& operator*=(mint61 rhs) { return *this = *this * rhs; }
  friend constexpr bool operator==(const mint61& lhs, const mint61& rhs) {
    return lhs.v == rhs.v;
  }
  friend ostream& operator<<(ostream& os, mint61 x) { return os << x.v; }
};

std::mt19937 RNG(std::chrono::system_clock::now().time_since_epoch().count());
unsigned long long RULL(unsigned long long L, unsigned long long R) {
  assert(L < R);
  return std::uniform_int_distribution<unsigned long long>(L, R - 1)(RNG);
}

using mint = mint61;
const mint B = mint(RULL(1, mint61::mod));


constexpr int MXSIZE = 100010;
mint powB[MXSIZE + 1], powB2wx[MXSIZE + 1];
auto init_Bs = [] {
  powB[0] = mint::raw(1);
  for (int i = 0; i < MXSIZE; i++) powB[i + 1] = powB[i] * B;
  return false;
}();


template <class T>
struct V {
  int i, j;
  T v;
};
struct Q { int il, ir, jl, jr; };
template <class T, class ResT=T>
auto rectangle_sum(vector<V<T>> points, vector<Q> queries) {
  ranges::sort(points, {}, &V<T>::i);
  vector<int> vc;
  vc.reserve(points.size());
  for (const auto& p : points) vc.emplace_back(p.j);
  ranges::sort(vc);
  vc.erase(unique(vc.begin(), vc.end()), vc.end());
  struct Ask {
    int i, iq;
    bool plus;
  };
  vector<Ask> asks(2 * queries.size());
  for (int iq = 0; iq < ssize(queries); iq++) {
    asks[2 * iq] = {queries[iq].il, iq, false};
    asks[2 * iq + 1] = {queries[iq].ir, iq, true};
  }
  ranges::sort(asks, {}, &Ask::i);
  const int sz = vc.size();
  vector<ResT> ft(sz);
  auto add = [&](int p, T x) {
    assert(0 <= p && p < sz);
    for (p++; p <= sz; p += p & -p) ft[p-1] += x;
  };
  auto sum = [&](int r) {
    assert(0 <= r && r <= sz);
    ResT s{};
    for (; r > 0; r -= r & -r) s += ft[r-1];
    return s;
  };
  int ptr = 0;
  vector<ResT> ans(queries.size());
  for (auto [i, iq, plus] : asks) {
    for (; ptr < ssize(points) && points[ptr].i < i; ptr++) {
      add(ranges::lower_bound(vc, points[ptr].j) - vc.begin(), points[ptr].v);
    }
    int l = ranges::lower_bound(vc, queries[iq].jl) - vc.begin();
    int r = ranges::lower_bound(vc, queries[iq].jr) - vc.begin();
    if (plus) ans[iq] += sum(r) - sum(l);
    else ans[iq] -= sum(r) - sum(l);
  }
  return ans;
}

} int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int h, w, n;
  cin >> h >> w >> n;
  powB2wx[0] = mint::raw(1);
  rep(i, MXSIZE) powB2wx[i+1] = powB2wx[i] * powB[w];
  auto f = [](int x) {
    if (x == 6) return 9;
    if (x == 9) return 6;
    return x;
  };
  vector<V<mint>> points1(n), points2(n);
  rep(t, n) {
    int i, j, x;
    cin >> i >> j >> x;
    i--, j--;
    points1[t] = {i, j, mint::raw(x) * powB2wx[i] * powB[j]};
    i = h - 1 - i, j = w - 1 - j, x = f(x);
    points2[t] = {i, j, mint::raw(x) * powB2wx[i] * powB[j]};
  }
  int q;
  cin >> q;
  vector<Q> queries1(q), queries2(q);
  for (int t = 0; t < q; t++) {
    int il, jl, ir, jr;
    cin >> il >> jl >> ir >> jr;
    il--, jl--;
    queries1[t] = {il, ir, jl, jr};
    queries2[t] = {h-ir, h-il, w-jr, w-jl};
  }
  auto sum1 = rectangle_sum(points1, queries1);
  auto sum2 = rectangle_sum(points2, queries2);
  for (int t = 0; t < q; t++) {
    mint v1 = sum1[t] * powB2wx[h - queries1[t].il] * powB[w - queries1[t].jl];
    mint v2 = sum2[t] * powB2wx[h - queries2[t].il] * powB[w - queries2[t].jl];
    cout << (v1 == v2 ? "Yes\n" : "No\n");
  }
}
0