結果
| 問題 |
No.3207 Digital Font
|
| コンテスト | |
| ユーザー |
 dp_ijk
|
| 提出日時 | 2025-07-18 23:35:58 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 15,419 bytes |
| コンパイル時間 | 3,790 ms |
| コンパイル使用メモリ | 279,100 KB |
| 実行使用メモリ | 53,556 KB |
| 最終ジャッジ日時 | 2025-07-18 23:36:33 |
| 合計ジャッジ時間 | 21,004 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 25 WA * 13 |
コンパイルメッセージ
In member function ‘WMSum<T, Weight_t>& WMSum<T, Weight_t>::operator=(WMSum<T, Weight_t>) [with T = int; Weight_t = modint61]’,
inlined from ‘void WMRectangleSum<Weight_t, x_lookup, y_lookup>::build() [with Weight_t = modint61; bool x_lookup = true; bool y_lookup = false]’ at main.cpp:335:12:
main.cpp:219:28: warning: ‘<anonymous>.WMSum<int, modint61>::log’ may be used uninitialized [-Wmaybe-uninitialized]
219 | N = wm.N, log = wm.log;
| ~~~^~~
main.cpp: In member function ‘void WMRectangleSum<Weight_t, x_lookup, y_lookup>::build() [with Weight_t = modint61; bool x_lookup = true; bool y_lookup = false]’:
main.cpp:335:14: note: ‘<anonymous>’ declared here
335 | wm = WMSum<int, Weight_t>(ny, W);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include <algorithm>
#include <array>
#include <bit>
#include <cassert>
#include <chrono>
#include <cmath>
#include <concepts>
#include <cstddef>
#include <cstdint>
#include <cstdlib>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <random>
#include <ranges>
#include <set>
#include <sstream>
#include <stdexcept>
#include <string>
#include <tuple>
#include <type_traits>
#include <utility>
#include <vector>
struct IOSetup {
IOSetup() {
std::cin.tie(nullptr);
std::ios::sync_with_stdio(false);
std::cout << std::fixed << std::setprecision(15);
std::cerr << std::fixed << std::setprecision(8);
}
};
IOSetup iosetup;
using int128_t = __int128;
using uint128_t = unsigned __int128;
template <typename T>
constexpr auto rep_iota_impl(T start, T stop) noexcept {
return std::views::iota(start, (start < stop ? stop : start));
}
template <typename T = int64_t>
constexpr auto rep_impl(auto stop) noexcept {
return rep_iota_impl<T>(0, stop);
}
template <class... Ts>
inline void read(Ts&... ts) {
(std::cin >> ... >> ts);
}
template <typename T>
void unique_inplace(std::vector<T>& A) {
if (!std::is_sorted(A.begin(), A.end())) { std::sort(A.begin(), A.end()); }
A.erase(std::unique(A.begin(), A.end()), A.end());
}
using std::vector;
template <typename X>
struct MAdd {
using ll = int64_t;
using T = X;
static constexpr T op(const T& x, const T& y) noexcept { return x + y; }
static constexpr T inverse(const T& x) noexcept { return -x; }
static constexpr T power(const T& x, ll n) noexcept { return T{x} * n; }
static constexpr T unit() noexcept { return T{}; }
static constexpr bool is_unit(const T& x) noexcept { return x == T{}; }
static constexpr bool commutative = true;
};
template <typename MX, typename T = typename MX::T, typename U>
vector<T> accumulate(vector<T> A, U initial) {
vector<T> res(A.size() + 1);
res[0] = T{initial};
for (const auto i : rep_impl((A.size()))) {
res[i + 1] = MX::op(res[i], A[i]);
}
return res;
}
template <typename T, typename U>
vector<T> accumulate(vector<T>& A, U initial) {
return accumulate<MAdd<T>>(A, initial);
}
using std::vector;
inline void put(const char* s) { std::cout << s; }
template <typename... Ts>
void print(const Ts&... ts) {
put(ts...);
std::cout << "\n";
}
using std::cin;
using std::cout;
using std::map;
using std::pair;
using std::set;
using std::string;
using std::tuple;
using std::vector;
using ll = int64_t;
using std::vector;
struct BitVector {
uint32_t N;
vector<std::pair<uint64_t, uint32_t>> data;
bool frozen = false;
int64_t ones = 0;
BitVector(int N_)
: N(N_),
data((N + 127) / 64) {}
void set(int i) {
assert(!frozen);
assert(0 <= i && i < N);
data[i / 64].first |= uint64_t{1} << (i % 64);
}
void build() {
assert(!frozen);
frozen = true;
for (const auto q : rep_impl((data.size() - 1))) {
data[q + 1].second = data[q].second + std::popcount(data[q].first);
}
ones = count1(N);
}
inline int count1(int k) const {
assert(frozen);
assert(0 <= k && k <= N);
return data[k / 64].second + std::popcount(data[k / 64].first & ((uint64_t{1} << (k % 64)) - 1));
}
inline int count0(int k) const { return k - count1(k); }
inline int count0() const {
assert(frozen);
return N - ones;
}
};
using std::pair;
using std::tuple;
using std::vector;
template <typename T, bool unique, bool lookup = false>
class Compress {
private:
vector<T> X;
vector<int> counter;
bool frozen = false;
public:
Compress() {}
template <typename U>
Compress(const vector<U>& A) {
extend(A);
}
void add(T x) {
frozen = false;
X.push_back(x);
}
template <typename U>
void extend(const vector<U>& A) {
frozen = false;
X.reserve(X.size() + A.size());
for (const auto& x : A) {
X.push_back(x);
}
}
void build() {
if (frozen) return;
if (!std::is_sorted(X.begin(), X.end())) { std::sort(X.begin(), X.end()); }
if constexpr (unique) { unique_inplace(X); }
if constexpr (lookup) {
if (!X.empty()) {
auto min_ = X.front();
auto max_ = X.back();
counter.resize(max_ - min_ + 1, 0);
for (const auto& x : X) {
counter[x - min_] += 1;
}
counter = accumulate(counter, 0);
}
}
frozen = true;
}
int64_t bisect_left(T x) const {
assert(frozen);
if (X.empty()) return 0;
if (x <= X.front()) return 0;
if (x > X.back()) return X.size();
if constexpr (lookup) {
return counter[x - X.front()];
} else {
return std::distance(X.begin(), std::lower_bound(X.begin(), X.end(), x));
}
}
int64_t bisect_right(T x) const {
assert(frozen);
if (X.empty()) return 0;
if (x < X.front()) return 0;
if (x >= X.back()) return X.size();
if constexpr (lookup) {
return counter[x - X.front() + 1];
} else {
return std::distance(X.begin(), std::upper_bound(X.begin(), X.end(), x));
}
}
int64_t size() const { return X.size(); }
T operator[](int64_t idx) const { return X[idx]; }
const vector<T>& sorted() const { return X; }
};
template <typename T, typename Weight_t>
struct WMSum {
using ll = int64_t;
int N, log;
vector<T> data;
T minval, maxval;
vector<BitVector> Vs;
vector<vector<Weight_t>> Ss;
vector<Weight_t> W;
WMSum() {}
WMSum(const vector<T>& A, const vector<Weight_t>& W)
: N(A.size()),
data(A),
W(W) {}
WMSum& operator=(WMSum wm) {
N = wm.N, log = wm.log;
data = wm.data;
Vs = wm.Vs;
Ss = wm.Ss;
W = wm.W;
return *this;
}
void build() {
log = 0;
if (N == 0) return;
minval = *min_element(data.begin(), data.end());
maxval = *max_element(data.begin(), data.end());
while ((T(1) << log) < (maxval - minval + 1))
log++;
vector<T> A = data;
for (auto& a : A) {
a -= minval;
}
vector<Weight_t> S(N + 1, 0);
for (int i = 0; i < N; i++) {
S[i + 1] += S[i] + W[i];
}
Ss.push_back(S);
vector<int> I(N);
for (int i = 0; i < N; i++)
I[i] = i;
for (int exp = log - 1; exp > -1; exp--) {
BitVector V(N);
vector<int> I0, I1;
for (int pos = 0; pos < N; pos++) {
auto i = I[pos];
auto a = A[i];
if ((a >> exp) & 1) {
I1.push_back(i);
V.set(pos);
} else {
I0.push_back(i);
}
}
V.build();
Vs.push_back(V);
I = I0;
I.insert(I.end(), I1.begin(), I1.end());
vector<Weight_t> S(N + 1, 0);
for (int pos = 0; pos < N; pos++) {
auto i = I[pos];
S[pos + 1] += S[pos] + W[i];
}
Ss.push_back(S);
}
std::reverse(Vs.begin(), Vs.end());
std::reverse(Ss.begin(), Ss.end());
}
Weight_t sum_lt(pair<int, int> Irange, T x) const {
auto [l, r] = Irange;
if (l < 0) l = 0;
if (r > N) r = N;
if (l >= r) return 0;
if (x < minval) return 0;
if (x > maxval) return Ss[log][r] - Ss[log][l];
x -= minval;
Weight_t res = 0;
for (int exp = log - 1; exp > -1; exp--) {
auto& S = Ss[exp];
auto& V = Vs[exp];
auto l0 = V.count0(l), r0 = V.count0(r);
if ((x >> exp) & 1) {
res += S[r0] - S[l0];
l += V.count0() - l0;
r += V.count0() - r0;
} else {
l = l0;
r = r0;
}
}
return res;
}
};
template <typename Weight_t, bool x_lookup = false, bool y_lookup = false>
struct WMRectangleSum {
using ll = int64_t;
vector<ll> X;
vector<ll> Y;
vector<Weight_t> W;
vector<tuple<ll, ll, Weight_t>> XYW;
Compress<ll, false, x_lookup> Cx;
Compress<ll, true, y_lookup> Cy_uniq;
bool frozen = false;
int length;
WMSum<int, Weight_t> wm;
vector<pair<ll, ll>> XY;
WMRectangleSum() {}
void register_point(ll x, ll y, Weight_t w) {
assert(!frozen);
XYW.push_back({x, y, w});
}
void build() {
assert(!frozen);
length = XYW.size();
std::sort(XYW.begin(), XYW.end());
X.reserve(length);
Y.reserve(length);
W.reserve(length);
for (auto [x, y, w] : XYW) {
X.push_back(x);
Y.push_back(y);
W.push_back(w);
Cx.add(x);
Cy_uniq.add(y);
}
XYW.clear();
Cx.build(), Cy_uniq.build();
vector<int> ny;
for (auto y : Y) {
ny.push_back(Cy_uniq.bisect_left(y));
}
wm = WMSum<int, Weight_t>(ny, W);
wm.build();
frozen = true;
}
Weight_t rectangle_sum(pair<ll, ll> Xrange, pair<ll, ll> Yrange) {
auto [x1, x2] = Xrange;
if (x1 >= x2) { return Weight_t{}; }
auto [y1, y2] = Yrange;
if (y1 >= y2) { return Weight_t{}; }
int i1 = Cx.bisect_left(x1), i2 = Cx.bisect_left(x2);
int j1 = Cy_uniq.bisect_left(y1), j2 = Cy_uniq.bisect_left(y2);
if (i1 >= i2) { return Weight_t{}; }
if (j1 >= j2) { return Weight_t{}; }
Weight_t res = wm.sum_lt({i1, i2}, j2);
res -= wm.sum_lt({i1, i2}, j1);
return res;
}
};
inline uint32_t nanoseconds() {
auto now = std::chrono::high_resolution_clock::now();
auto duration = now.time_since_epoch();
auto nanoseconds = std::chrono::duration_cast<std::chrono::nanoseconds>(duration);
uint32_t rv = nanoseconds.count();
return rv;
}
inline uint32_t randtime32() {
static constexpr uint64_t MULT = 0x9E3779B97F4A7C15;
static uint64_t rv = 123456789;
rv ^= nanoseconds();
for (int i = 0; i < 20; ++i) {
rv ^= rv << 13, rv ^= rv >> 17, rv ^= rv << 5;
rv *= MULT;
rv *= i * i + 1;
rv += 1;
}
return uint32_t(rv);
}
inline uint64_t randtime64() { return uint64_t(randtime32()) << 32 | randtime32(); }
inline uint64_t random64() {
using uint128_t = __uint128_t;
static constexpr uint64_t MULT = 0xfeb3'4465'7c0a'f413;
static uint64_t x2 = randtime64();
static uint64_t x3 = 0xcafe'f00d'd15e'a5e5;
static uint128_t c_x1 = uint128_t(0x1405'7b7e'f767'814f) << 64 | randtime64();
uint128_t x = (uint128_t)(x3)*MULT;
uint64_t result = (x3 ^ x2) + ((uint64_t)(c_x1) ^ (uint64_t)(x >> 32));
x3 = x2;
x2 = (uint64_t)(c_x1);
c_x1 = x + (c_x1 >> 64);
return result;
}
inline uint64_t random64(uint64_t stop) {
assert(stop > 0);
return random64() % stop;
}
inline uint64_t random64(uint64_t start, uint64_t stop) {
assert(start < stop);
return start + random64(stop - start);
}
struct modint61 {
static constexpr uint64_t MOD = (1ULL << 61) - 1;
using mint = modint61;
using uint128_t = __uint128_t;
private:
uint64_t _v = 0;
static constexpr uint64_t pow_mod(uint64_t base, uint64_t exp) noexcept {
uint64_t res = 1;
while (exp) {
if (exp & 1) {
const uint128_t y = static_cast<uint128_t>(res) * base;
res = (y >> 61) + (y & MOD);
if (res >= MOD) res -= MOD;
}
const uint128_t y = static_cast<uint128_t>(base) * base;
base = (y >> 61) + (y & MOD);
if (base >= MOD) base -= MOD;
exp >>= 1;
}
return res;
}
public:
static constexpr mint raw(uint64_t v) noexcept {
mint a;
a._v = v;
return a;
}
constexpr modint61() {}
constexpr modint61(int32_t v)
: _v(v < 0 ? v + MOD : v) {}
constexpr modint61(uint64_t v)
: _v(v % MOD) {}
constexpr mint& operator+=(mint rhs) {
if (_v >= MOD - rhs._v) _v -= MOD;
_v += rhs._v;
return *this;
}
constexpr mint& operator-=(mint rhs) {
if (_v < rhs._v) _v += MOD;
_v -= rhs._v;
return *this;
}
constexpr mint& operator*=(mint rhs) {
const uint128_t y = static_cast<uint128_t>(_v) * rhs._v;
_v = (y >> 61) + (y & MOD);
if (_v >= MOD) _v -= MOD;
return *this;
}
constexpr mint& operator/=(mint rhs) {
const uint128_t y = static_cast<uint128_t>(_v) * pow_mod(rhs._v, MOD - 2);
_v = (y >> 61) + (y & MOD);
if (_v >= MOD) _v -= MOD;
return *this;
}
friend constexpr mint operator+(mint lhs, mint rhs) { return lhs += rhs; }
friend constexpr mint operator-(mint lhs, mint rhs) { return lhs -= rhs; }
friend constexpr mint operator*(mint lhs, mint rhs) { return lhs *= rhs; }
bool operator<(const mint& other) const { return _v < other._v; }
bool operator==(const mint& p) const { return _v == p._v; }
bool operator!=(const mint& p) const { return _v != p._v; }
mint inv() const { return pow(MOD - 2); }
mint pow(int64_t n) const {
if (n < 0) return inv().pow(-n);
return mint::raw(pow_mod(_v, n));
}
};
using mint = modint61;
int main() {
int64_t H, W;
read(H, W);
int64_t N;
read(N);
vector<mint> A(10);
for (const auto i : rep_impl((10)))
A[i] = mint::raw(random64(1, uint64_t{1} << 60));
const mint base = mint::raw(random64(1, uint64_t{1} << 60));
const mint base2 = mint::raw(random64(1, uint64_t{1} << 60));
vector<ll> F(10);
for (const auto i : rep_impl((10)))
F[i] = i;
F[6] = 9;
F[9] = 6;
vector<tuple<ll, ll, ll>> todo;
for ([[maybe_unused]] const auto _i : rep_impl((N))) {
int64_t i, j, x;
read(i, j, x);
i -= 1;
j -= 1;
todo.push_back({i, j, x});
}
auto wm = WMRectangleSum<mint, 1, 0>();
auto wm2 = WMRectangleSum<mint, 1, 0>();
for (auto [i, j, x] : todo) {
wm.register_point(i, j, mint{A[x]} * base.pow(i) * base2.pow(j));
ll ni = H - 1 - i, nj = W - 1 - j;
wm2.register_point(ni, nj, mint{A[F[x]]} * base.pow(ni) * base2.pow(nj));
}
wm.build();
wm2.build();
int64_t Q;
read(Q);
for ([[maybe_unused]] const auto _i : rep_impl((Q))) {
int64_t L, D, R, U;
read(L, D, R, U);
L -= 1;
D -= 1;
mint hash = wm.rectangle_sum({L, R}, {D, U});
hash /= base.pow(L) * base2.pow(D);
mint hash2 = wm2.rectangle_sum({H - R, H - L}, {W - U, W - D});
hash2 /= base.pow(H - R) * base2.pow(W - U);
if (hash == hash2) {
print("Yes");
} else {
print("No");
}
}
}