結果
| 問題 |
No.3207 Digital Font
|
| コンテスト | |
| ユーザー |
 pitP
|
| 提出日時 | 2025-07-18 23:59:05 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,507 bytes |
| コンパイル時間 | 7,412 ms |
| コンパイル使用メモリ | 334,872 KB |
| 実行使用メモリ | 236,080 KB |
| 最終ジャッジ日時 | 2025-07-18 23:59:18 |
| 合計ジャッジ時間 | 12,761 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | TLE * 1 -- * 37 |
ソースコード
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
istream &operator>>(istream &is, modint &a) { long long v; is >> v; a = v; return is; }
ostream &operator<<(ostream &os, const modint &a) { return os << a.val(); }
istream &operator>>(istream &is, modint998244353 &a) { long long v; is >> v; a = v; return is; }
ostream &operator<<(ostream &os, const modint998244353 &a) { return os << a.val(); }
istream &operator>>(istream &is, modint1000000007 &a) { long long v; is >> v; a = v; return is; }
ostream &operator<<(ostream &os, const modint1000000007 &a) { return os << a.val(); }
typedef long long ll;
typedef vector<vector<int>> Graph;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define FOR(i,l,r) for (int i = l;i < (int)(r); i++)
#define rep(i,n) for (int i = 0;i < (int)(n); i++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define my_sort(x) sort(x.begin(), x.end())
#define my_max(x) *max_element(all(x))
#define my_min(x) *min_element(all(x))
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = (1<<30) - 1;
const ll LINF = (1LL<<62) - 1;
const int MOD = 998244353;
const int MOD2 = 1e9+7;
const double PI = acos(-1);
vector<int> di = {1,0,-1,0};
vector<int> dj = {0,1,0,-1};
#ifdef LOCAL
# include <debug_print.hpp>
# define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)
#else
# define debug(...) (static_cast<void>(0))
#endif
static const int B = 3;
long long base_p[B] = {114514, 1919, 810};
long long base_q[B] = {765, 961, 283};
long long mod[B] = {1000000007, 1000000009, 998244353};
template <class S, S (*op)(S, S), S (*e)(), class CoordinateType> struct RangeTree {
using CT = CoordinateType;
using Point = pair<CT, CT>;
vector<Point> points;
vector<vector<Point>> yx;
vector<atcoder::segtree<S,op,e>> seg;
int n;
void _set(int idx, Point p, S val){
int i = lower_bound(yx[idx].begin(), yx[idx].end(), Point{p.second, p.first}) - yx[idx].begin();
seg[idx].set(i, val);
}
S _prod(int idx, CT yl, CT yr){
auto comp = [](const Point &lhs, const Point &rhs) {return lhs.first < rhs.first; };
int il = lower_bound(yx[idx].begin(), yx[idx].end(), Point{yl, yl}, comp) - yx[idx].begin();
int ir = lower_bound(yx[idx].begin(), yx[idx].end(), Point{yr, yr}, comp) - yx[idx].begin();
return seg[idx].prod(il, ir);
}
void add_point(CT x, CT y){
points.push_back(Point{x, y});
}
void build(){
sort(points.begin(), points.end());
points.erase(unique(points.begin(), points.end()), points.end());
n = points.size();
yx.resize(2 * n);
for(int i = 0; i < n; i++) yx[i + n] = { Point{points[i].second, points[i].first}};
for(int i = n - 1; i > 0; i--){
auto &lc = yx[2 * i];
auto &rc = yx[2 * i + 1];
merge(lc.begin(), lc.end(), rc.begin(), rc.end(), back_inserter(yx[i]));
yx[i].erase(unique(yx[i].begin(), yx[i].end()), yx[i].end());
}
for(const auto &v : yx) seg.emplace_back(v.size());
}
void set(CT x, CT y, S val){
int i = lower_bound(points.begin(), points.end(), Point{x, y}) - points.begin() + n;
while(i){
_set(i, Point{x, y}, val);
i = i >> 1;
}
}
S prod(CT xl, CT xr, CT yl, CT yr){
auto comp = [](const Point &lhs, const Point &rhs) {return lhs.first < rhs.first; };
int l = lower_bound(points.begin(), points.end(), Point{xl, yr}, comp) - points.begin() + n;
int r = lower_bound(points.begin(), points.end(), Point{xr, yr}, comp) - points.begin() + n;
S sml = e(), smr = e();
while(l < r){
if(l & 1) sml = op(sml, _prod(l++, yl, yr));
if(r & 1) smr = op(_prod(--r, yl, yr), smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S get(CT x, CT y){
return prod(x, x + 1, y, y + 1);
}
};
using S = array<long long, B>;
S e(){ return S{0, 0, 0}; }
S op(S a, S b){
S ret = e();
rep(i, B) ret[i] = (ret[i] + a[i]) % mod[i];
rep(i, B) ret[i] = (ret[i] + b[i]) % mod[i];
return ret;
}
int main(){
cin.tie(0);
ios_base::sync_with_stdio(false);
int H, W;
cin >> H >> W;
vector pw_p(B, vector<ll>(W + 1, 1));
vector pw_q(B, vector<ll>(H + 1, 1));
rep(b, B) {
rep(i, W) pw_p[b][i + 1] = (pw_p[b][i] * base_p[b]) % mod[b];
rep(i, H) pw_q[b][i + 1] = (pw_q[b][i] * base_q[b]) % mod[b];
}
int N; cin >> N;
vector A_(H, vector<pii>{});
vector B_(H, vector<pii>{});
rep(i, N) {
int r, c, x;
cin >> r >> c >> x;
r--, c--;
if(x == 0) continue;
x += 1;
if(x == 7) {
A_[r].push_back({c, 7});
B_[H - 1 - r].push_back({W - 1 - c, 10});
}
else if(x == 10){
A_[r].push_back({c, 10});
B_[H - 1 - r].push_back({W - 1 - c, 7});
}
else{
A_[r].push_back({c, x});
B_[H - 1 - r].push_back({W - 1 - c, x});
}
}
RangeTree<S, op, e, int> rta, rtb;
rep(r, H)for(auto &[c, x] : A_[r]) rta.add_point(r, c);
rep(r, H)for(auto &[c, x] : B_[r]) rtb.add_point(r, c);
rta.build();
rtb.build();
rep(r, H)for(auto &[c, x] : A_[r]) {
S v = e();
rep(b, B) v[b] = (((x * pw_p[b][c]) % mod[b]) * pw_q[b][r]) % mod[b];
rta.set(r, c, v);
}
rep(r, H)for(auto &[c, x] : B_[r]) {
S v = e();
rep(b, B) v[b] = (((x * pw_p[b][c]) % mod[b]) * pw_q[b][r]) % mod[b];
rtb.set(r, c, v);
}
int Q; cin >> Q;
rep(q, Q){
int l, d, r, u;
cin >> l >> d >> r >> u;
l--, d--;
S va = rta.prod(l, r, d, u);
S vb = rtb.prod(H - r, H - l, W - u, W - d);
int h = H - r - l, w = W - u - d;
if(h > 0){
rep(b, B) va[b] = (va[b] * pw_q[b][h]) % mod[b];
}
else{
rep(b, B) vb[b] = (vb[b] * pw_q[b][-h]) % mod[b];
}
if(w > 0){
rep(b, B) va[b] = (va[b] * pw_p[b][w]) % mod[b];
}
else{
rep(b, B) vb[b] = (vb[b] * pw_p[b][-w]) % mod[b];
}
cout << (va == vb ? "Yes" : "No") << "\n";
}
}