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

• 問題: No.3530 「」
• ユーザー: tassei903
• 提出日時: 2026-05-04 23:04:06
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 1,810 ms / 3,000 ms
• コード長: 7,729 bytes
• コンパイル時間: 2,990 ms
• コンパイル使用メモリ: 363,372 KB
• 実行使用メモリ: 39,556 KB
• 最終ジャッジ日時: 2026-05-04 23:04:37
• 合計ジャッジ時間: 27,400 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

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

ソースコード

#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);

    
    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});
            }
        }

    }
    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();
    }
    
}