#1149633 (C++23) No.3530 「」

• 問題: No.3530 「」
• ユーザー: aa36
• 提出日時: 2026-02-27 12:06:02
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 495 ms / 3,000 ms
• コード長: 4,349 bytes
• コンパイル時間: 3,938 ms
• コンパイル使用メモリ: 361,232 KB
• 実行使用メモリ: 16,908 KB
• 最終ジャッジ日時: 2026-05-04 20:50:44
• 合計ジャッジ時間: 15,820 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_1

ファイルパターン	結果
sample	AC * 2
other	AC * 27

ソースコード

#include<bits/stdc++.h>
using namespace std;
using ll = long long;//int型は使わない
using pll = pair<ll , ll>;
using vl = vector<ll> ; //1D
using vvl = vector<vl> ;//2D
using vvvl = vector<vvl> ;//3D
using vvvvl = vector<vvvl>;//4D
using vvvvvl = vector<vvvvl>;//5D
using vvvvvvl = vector<vvvvvl>;//6D
using vvvvvvvl = vector<vvvvvvl>;//7D
using vp = vector<pll> ; //1D
using vvp = vector<vp> ;//2D
using vvvp = vector<vvp> ;//3D
using vvvvp = vector<vvvp>;//4D
using vvvvvp = vector<vvvvp>;//5D
using vvvvvvp = vector<vvvvvp>;//6D
using vvvvvvvp = vector<vvvvvvp>;//7D
using vi = vector<int> ; //1D
using vvi = vector<vi> ;//2D
using vvvi = vector<vvi> ;//3D
using vvvvi = vector<vvvi>;//4D
using vvvvvi = vector<vvvvi>;//5D
using vvvvvvi = vector<vvvvvi>;//6D
using vvvvvvvi = vector<vvvvvvi>;//7D
using vb = vector<bool> ; //1D
using vvb = vector<vb> ;//2D
using vvvb = vector<vvb> ;//3D
using vvvvb = vector<vvvb>;//4D
using vvvvvb = vector<vvvvb>;//5D
using vvvvvvb = vector<vvvvvb>;//6D
using vvvvvvvb = vector<vvvvvvb>;//7D
using vs = vector<string> ; //1D
using vvs = vector<vs> ;//2D
using vvvs = vector<vvs> ;//3D
using vvvvs = vector<vvvs>;//4D
using vvvvvs = vector<vvvvs>;//5D
using vvvvvvs = vector<vvvvvs>;//6D
using vvvvvvvs = vector<vvvvvvs>;//7D
[[maybe_unused]] const ll INF = 2e18 ;
[[maybe_unused]] const ll MOD = 998244353;
#define rep(i,a,b) for(ll i=(ll)a; i<(ll)b; i++)
#define rrep(i,a,b) for(ll i=(ll)b-1; i>=(ll)a; i--)
#define all(vec1) (vec1).begin(), (vec1).end()
#define yn(b,ex) if(1){if(b)cout << "Yes" << endl;else cout << "No" << endl ;if(ex)return 0;}
#define debug(var) cerr << #var << " : " << var << endl;

//fastio
struct FastIO {
    FastIO() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
    }
} fastio;
//あまり(負の数対応)
template<typename T>
T ovr(T a,T b){
  T ret=a%b;
  if(ret<0)ret+=b;
  return ret;
}
const string MOD_bi = "111111111111111111111110110111";
//MOD下での逆元
ll minv(ll ina){
  ll a = ina % MOD;
  ll ret = 1;
  ll V = a;
  rep(i,0,MOD_bi.size()){
    if(MOD_bi[i]=='1')ret=(ret*V)%MOD;
    V=(V*V)%MOD;
  }
  return ret;
}

//指数をある値で割った余り
ll mpow(ll a , ll b , ll M){
    ll ret = 1;
    ll V = a;
    rep(i,0,64){
        if((b >> i) & 1)ret=(ret*V)%M;
        V=(V*V)%M;
    }
    return ret;
}
template<typename T>
bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template<typename T>
bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
/////////main/////////
#include<atcoder/lazysegtree>
#include<atcoder/modint>
using namespace atcoder;
using mint = modint998244353;
using S = pair<mint, mint>; // a * (1 - b)
S op(S a, S b) {
   return {a.first * (1 - a.second) + b.first * (1 - b.second), 0};
}
S e() {
   return {1, 1};
}
using F = mint;
S mapping (F f, S x) {
   x.first *= f;
   return x;
}
F composition(F f, F g) {
   return f * g;
}
F id() {
   return mint(1);
}
int main()
{
   mint f34 = mint(3) / mint(4);
   mint f43 = 1 / f34;
   int N; cin >> N;
   vl X(N), Y(N);
   rep(i,0,N) cin >> X[i] >> Y[i];
   vl zX = X, zY = Y;
   sort(all(zX)), sort(all(zY));
   zX.erase(unique(all(zX)), zX.end());
   zY.erase(unique(all(zY)), zY.end());
   vl rX(N), rY(N);
   rep(i,0,N) rX[i] = lower_bound(all(zX), X[i]) - zX.begin();
   rep(i,0,N) rY[i] = lower_bound(all(zY), Y[i]) - zY.begin();
   if (zX.size() == 1 || zY.size() == 1) { cout << 0 << endl; return 0; }
   mint ans = 0;
   rep(_,0,2) {
      vvl G(zX.size()); rep(i,0,N) G[rX[i]].push_back(rY[i]);
      // seg木の初期化
      vector<S> V(zY.size(), e());
      rep(i,0,N) if (rY[i] + 1 < zY.size()) V[rY[i] + 1].first *= f34;
      rep(i,1,zY.size()) V[i].first *= V[i-1].first;
      lazy_segtree<S, op, e, F, mapping, composition, id> seg(V);
      mint fs = 1;
      rep(i,0,zX.size()-1) {
         for (auto y : G[i]) {
            seg.set(y, {seg.get(y).first, seg.get(y).second * f34});
            seg.apply(0, y, f34);
            seg.apply(y + 1, zY.size(), f43);
            fs *= f34;
         }
         auto all_prd = seg.all_prod();
         ans += (mint(1) - all_prd.first * (1 - all_prd.second) - fs) * (zX[i + 1] - zX[i]);
      }

      swap(rX, rY);
      swap(zX, zY);
   }
   rep(i,0,N) ans *= 4;
   cout << (ans * 2).val() << endl;
    return 0;
}