結果
| 問題 | No.3530 「」 |
| コンテスト | |
| ユーザー |
 tassei903
|
| 提出日時 | 2026-05-04 22:59:20 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,038 bytes |
| 記録 | |
| コンパイル時間 | 2,947 ms |
| コンパイル使用メモリ | 363,260 KB |
| 実行使用メモリ | 38,132 KB |
| 最終ジャッジ日時 | 2026-05-04 22:59:49 |
| 合計ジャッジ時間 | 25,673 ms |
|
ジャッジサーバーID （参考情報） |
judge1_1 / judge3_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | WA * 2 |
| other | AC * 1 WA * 26 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define ov4(a, b, c, d, name, ...) name
#define rep3(i, a, b, c) for(ll i = (a); i < (b); i += (c))
#define rep2(i, a, b) rep3(i, a, b, 1)
#define rep1(i, n) rep2(i, 0, n)
#define rep0(n) rep1(aaaaa, n)
#define rep(...) ov4(__VA_ARGS__, rep3, rep2, rep1, rep0)(__VA_ARGS__)
#define per(i, a, b) for(ll i = (a)-1; i >= (b); i--)
#define fore(e, v) for(auto&& e : v)
#define all(a) begin(a), end(a)
#define sz(a) (int)(a.size())
#define lb(v, x) (lower_bound(all(v), x) - begin(v))
#define eb emplace_back
template<typename T, typename S> bool chmin(T& a, const S& b) { return a > b ? a = b, 1 : 0; }
template<typename T, typename S> bool chmax(T& a, const S& b) { return a < b ? a = b, 1 : 0; }
const int INF = 1e9 + 100;
const ll INFL = 3e18 + 100;
#define i128 __int128_t
struct _ {
_() { cin.tie(0)->sync_with_stdio(0), cout.tie(0); }
} __;
void debug(auto ...vs) {
((cerr << vs << " "), ...) << endl;
}
using U = uint64_t;
template<class S, S (*op)(S, S), S (*e)(), class F, S (*mpp)(F, S), F (*cmpo)(F, F), F (*id)()> struct lazy_segtree {
lazy_segtree() : lazy_segtree(0) {}
explicit lazy_segtree(int n) : lazy_segtree(vector<S>(n, e())) {}
explicit lazy_segtree(const vector<S>& v) : n(sz(v)) {
s = bit_ceil(U(n));
log = countr_zero(U(s));
d = vector<S>(2 * s, e());
lz = vector<F>(s, id());
rep(i, n) d[s + i] = v[i];
per(i, s, 1) update(i);
}
void set(int p, S x) {
p += s;
PUSH(p);
d[p] = x;
rep(i, 1, log + 1) update(p >> i);
}
S get(int p) {
p += s;
PUSH(p);
return d[p];
}
S prod(int l, int r) {
if(l == r) return e();
l += s, r += s;
per(i, log + 1, 1) {
if(((l >> i) << i) != l) push(l >> i);
if(((r >> i) << i) != r) push((r - 1) >> i);
}
S sml = e(), smr = e();
while(l < r) {
if(l & 1) sml = op(sml, d[l++]);
if(r & 1) smr = op(d[--r], smr);
l >>= 1, r >>= 1;
}
return op(sml, smr);
}
S all_prod() { return d[1]; }
void apply(int p, F f) {
// assert(0 <= p && p < n);
p += s;
PUSH(p);
d[p] = mpp(f, d[p]);
rep(i, 1, log + 1) update(p >> i);
}
void apply(int l, int r, F f) {
// assert(0 <= l && l <= r && r <= _n);
if(l == r) return;
l += s, r += s;
per(i, log + 1, 1) {
if(((l >> i) << i) != l) push(l >> i);
if(((r >> i) << i) != r) push((r - 1) >> i);
}
int ml = l, mr = r;
while(l < r) {
if(l & 1) all_apply(l++, f);
if(r & 1) all_apply(--r, f);
l >>= 1, r >>= 1;
}
l = ml, r = mr;
rep(i, 1, log + 1) {
if(((l >> i) << i) != l) update(l >> i);
if(((r >> i) << i) != r) update((r - 1) >> i);
}
}
template<class G> int max_right(int l, G g) {
assert(g(e()));
if(l == n) return n;
l += s;
PUSH(l);
S sm = e();
do {
while(~l & 1) l >>= 1;
if(!g(op(sm, d[l]))) {
while(l < s) {
push(l);
l <<= 1;
if(g(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - s;
}
sm = op(sm, d[l]);
l++;
} while((l & -l) != l);
return n;
}
template<class G> int min_left(int r, G g) {
assert(g(e()));
if(r == 0) return 0;
r += s;
PUSH(r - 1);
S sm = e();
do {
r--;
while(r > 1 && r & 1) r >>= 1;
if(!g(op(d[r], sm))) {
while(r < s) {
push(r);
r = (2 * r + 1);
if(g(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - s;
}
sm = op(d[r], sm);
} while((r & -r) != r);
return 0;
}
S operator[](int k) { return get(k); }
int len() { return n; }
private:
int n, s, log;
vector<S> d;
vector<F> lz;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
void all_apply(int k, F f) {
d[k] = mpp(f, d[k]);
if(k < s) lz[k] = cmpo(f, lz[k]);
}
void push(int k) {
all_apply(2 * k, lz[k]);
all_apply(2 * k + 1, lz[k]);
lz[k] = id();
}
void PUSH(int k) { per(i, log + 1, 1) push(k >> i); }
};
constexpr int mod = 998244353;
struct mint {
int x;
mint(ll x_ = 0) : x(x_ % mod) {
if(x < 0) x += mod;
}
mint operator-() {
auto res = *this;
res.x = (x ? mod - x : 0);
return res;
}
mint& operator+=(mint r) {
if((x += r.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(mint r) {
if((x -= r.x) < 0) x += mod;
return *this;
}
mint& operator*=(mint r) {
x = 1LL * x * r.x % mod;
return *this;
}
mint& operator/=(mint r) { return *this *= r.inv(); }
friend mint operator+(mint a, mint b) { return a += b; }
friend mint operator-(mint a, mint b) { return a -= b; }
friend mint operator*(mint a, mint b) { return a *= b; }
friend mint operator/(mint a, mint b) { return a /= b; }
mint inv() const { return pow(mod - 2); }
mint pow(ll b) const {
mint a = *this, c = 1;
while(b) {
if(b & 1) c *= a;
a *= a;
b >>= 1;
}
return c;
}
};
using vm = vector<mint>;
struct S {
mint val, len;
};
S op(S x, S y) {
return S{x.val + y.val, x.len + y.len};
}
S e() {
return {0, 0};
}
struct F {
mint a, b;
};
S mapp(F f, S x) {
return {f.a * x.val + f.b * x.len, x.len};
}
F comp(F f, F g) {
return {f.a * g.a, f.b + f.a * g.b};
}
F id() {
return {1, 0};
}
mint sub(vi& a, vi& b, int dx, int dy) {
const int LIM = 1e9 + 10;
const mint m34 = mint(3) * (mint(4).inv()), INV34 = mint(4) * (mint(3).inv());
if (dy == 1) {
swap(a, b);
swap(dx, dy);
}
int n = sz(a);
vi idx(n);iota(all(idx), 0);
vi ys = b;
sort(all(ys));ys.emplace_back(LIM);
sort(all(idx), [&](int i, int j){return b[i] < b[j]; });
vector<S> vs1(n), vs2(n);
rep(i, n) {
vs1[i] = S{ys[i+1] - ys[i], ys[i+1] - ys[i]};
vs2[i] = S{m34.pow(i + 1) * (ys[i+1] - ys[i]), ys[i+1] - ys[i]};
}
lazy_segtree<S, op, e, F, mapp, comp, id> lst1(vs1);
lazy_segtree<S, op, e, F, mapp, comp, id> lst2(vs2);
lazy_segtree<S, op, e, F, mapp, comp, id> lst3(vs2);
// cerr << "! ";
// rep(i, n) {
// cerr << lst1.get(i).val.x << " " << lst1.get(i).len.x << " , ";
// }
// cerr << endl;
map<int, vi> eve;
rep(i, n) {
eve[a[idx[i]]].emplace_back(i);
eve[a[idx[i]] - dx].emplace_back(i + n);
}
mint res = 0;
int last = -LIM;
for (auto [x, que] : eve) {
mint ls = x - last;
last = x;
res += (ys.back() - ys.front() - lst1.all_prod().val - lst2.all_prod().val + lst3.all_prod().val) * ls;
fore(i, que) {
if (i < n) {
lst1.apply(0, i, F{m34, 0});
lst3.apply(0, i, F{m34, 0});
}
else {
i -= n;
lst2.apply(i, n, F{INV34, 0});
lst3.apply(i, n, F{INV34, 0});
}
}
// rep(i, n) {
// cerr << lst1.get(i).val.x << " ";
// }
// cerr << endl;
}
// cerr << (res * mint(4).pow(n)).x << endl;
return res;
}
void solve() {
int n;cin >> n;
vi a(n), b(n);
rep(i, n) cin >> a[i] >> b[i];
// sub(a, b, 0, 0);
mint res = 4 * sub(a, b, 0, 0) - 2 * sub(a, b, 1, 0) - 2 * sub(a, b, 0, 1);
cout << (res * (mint(4).pow(n))).x << endl;
}
int main(){
int T = 1;
// int T;cin >> T;
while(T--) {
solve();
}
}