Submission #6798138


Source Code Expand

Copy
#include <bits/stdc++.h>

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, a, b) for (ll i = (a); i < (b); i++)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;

template <std::uint64_t M>
class modint {
 public:
  uint64_t a;

  explicit constexpr modint(const uint64_t x = 0) noexcept : a(x % M) {}
  constexpr uint64_t &value() noexcept { return a; }
  constexpr const uint64_t &value() const noexcept { return a; }
  constexpr modint operator+(const modint rhs) const noexcept {
    return modint(*this) += rhs;
  }
  constexpr modint operator-(const modint rhs) const noexcept {
    return modint(*this) -= rhs;
  }
  constexpr modint operator*(const modint rhs) const noexcept {
    return modint(*this) *= rhs;
  }
  constexpr modint operator/(const modint rhs) const noexcept {
    return modint(*this) /= rhs;
  }
  constexpr modint &operator+=(const modint rhs) noexcept {
    a += rhs.a;
    if (a >= M) {
      a -= M;
    }
    return *this;
  }
  constexpr modint &operator-=(const modint rhs) noexcept {
    if (a < rhs.a) {
      a += M;
    }
    a -= rhs.a;
    return *this;
  }
  constexpr modint &operator*=(const modint rhs) noexcept {
    a = a * rhs.a % M;
    return *this;
  }
  constexpr modint &operator/=(modint rhs) noexcept {
    uint64_t exp = M - 2;
    while (exp) {
      if (exp % 2) {
        *this *= rhs;
      }
      rhs *= rhs;
      exp /= 2;
    }
    return *this;
  }
};

using mint = modint<998244353>;

template <typename T>
class SegTree {
 private:
    int _n;
    T _init_val;
    std::vector<T> _data;
    std::function<T(T, T)> _f;

    T _query(int a, int b, int k, int l, int r) {
        // [a b)と[l r]が交差しない
        if (r <= a || b <= l) return _init_val;

        // [a b)が[l r]を含む
        if (a <= l && r <= b) return _data[k];

        T vl = _query(a, b, k*2+1, l, (l+r)/2);
        T vr = _query(a, b, k*2+2, (l+r)/2, r);

        return _f(vl, vr);
    }

 public:
    SegTree(int n, T init_val, std::function<T(T, T)> f) {
        _init_val = init_val;
        _n = 1;
        _f = f;

        while (_n < n)
            _n *= 2;
        _data.resize(2 * _n, init_val);
    }

    T get(int k) {
        return _data[k + _n - 1];
    }

    void update(int k, T a) {
        k += _n-1;
        _data[k] = a;
        while (k > 0) {
            k = (k-1)/2;
            _data[k] = _f(_data[k*2+1], _data[k*2+2]);
        }
    }

    // [a b)の範囲でfを適用
    T query(int a, int b) {
        return _query(a, b, 0, 0, _n);
    }

    // 先頭からチェックし,はじめてxを満たしたインデックス
    int lower_bound(T x) {
        return _lower_bound(x, 0);
    }

    int _lower_bound(T x, int k) {
        if (k >= _n-1) {
            return k - (_n - 1);  // 葉
        } else if (_data[k] < x) {
            return _n;  // 該当なし
        } else if (x <= _data[k * 2 + 1]) {
            return _lower_bound(x, k * 2 + 1);
        } else {
            return _lower_bound(x - _data[k * 2 + 1] , k * 2 + 2);
        }
    }
};

mint pow2(ll n) {
  if (n==0) {
    return mint(1);
  } else if (n%2 == 0) {
    auto x = pow2(n/2);
    return x * x;
  } else {
    return pow2(n-1) * mint(2);
  }
}

signed main() {
  ll N;
  cin>>N;

  vector<PLL> p(N); // {x,y}
  rep(i,N)
    cin >> p[i].first >> p[i].second;

  sort(begin(p), end(p));

  // Y座標を圧縮 0 <= y <= 200000
  {
    set<ll> ys;
    rep(i,N)
      ys.insert(p[i].second);
    ll i = 0;
    map<ll,ll> mp;
    for (auto y: ys){
      mp[y] = i++;
    }
    rep(i,N)
      p[i].second = mp[p[i].second];
  }

  vector<ll> a(N), b(N), c(N), d(N); // a[i]: i番目のときに領域Aに含まれる点の数
  {
    SegTree<ll> st(200010, 0, [](ll x, ll y){ return x+y; });
    rep(i,N){
      c[i] = st.query(0, p[i].second);
      a[i] = st.query(p[i].second, 200010);
      st.update(p[i].second, 1);
    }
  }
  {
    SegTree<ll> st(200010, 0, [](ll x, ll y){ return x+y; });
    for (int i=N-1; i>=0; i--) {
      d[i] = st.query(0, p[i].second);
      b[i] = st.query(p[i].second, 200010);
      st.update(p[i].second, 1);
    }
  }
  //rep(i,N){
  //  printf("a[%d]=%d c[%d]=%d b[%d]=%d d[%d]=%d\n", i, a[i], i, c[i], i, b[i], i, d[i]);
  //}

  mint ans(0);
  rep(i,N) {
    // 1. 点iを含まない場合
    // e[a-d]: 各領域に1個以上の要素を含めるかどうか
    rep(ea, 2) rep(eb, 2) rep(ec, 2) rep(ed, 2) {
      if ((ea|ec) & (eb|ed) & (ea|eb) & (ec|ed)) {
        mint t(1);
        if (ea) t *= pow2(a[i])-mint(1);
        if (eb) t *= pow2(b[i])-mint(1);
        if (ec) t *= pow2(c[i])-mint(1);
        if (ed) t *= pow2(d[i])-mint(1);
        ans += t;
      }
    }

    // 2. 点iを含む場合
    ans += pow2(a[i]) * pow2(b[i]) * pow2(c[i]) * pow2(d[i]);
  }
  cout << ans.value() << endl;
  return 0;
}

Submission Info

Submission Time
Task F - Enclosed Points
User bobuhiro11
Language C++14 (GCC 5.4.1)
Score 600
Code Size 5096 Byte
Status
Exec Time 1357 ms
Memory 25216 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 s1.txt, s2.txt, s3.txt
All 600 / 600 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt 3 ms 4352 KB
02.txt 3 ms 4352 KB
03.txt 3 ms 4352 KB
04.txt 3 ms 4352 KB
05.txt 3 ms 4352 KB
06.txt 3 ms 4352 KB
07.txt 3 ms 4352 KB
08.txt 3 ms 4352 KB
09.txt 3 ms 4476 KB
10.txt 3 ms 4352 KB
11.txt 1314 ms 24832 KB
12.txt 1280 ms 24448 KB
13.txt 1325 ms 25216 KB
14.txt 1254 ms 24064 KB
15.txt 1344 ms 25216 KB
16.txt 1329 ms 25216 KB
17.txt 1345 ms 25216 KB
18.txt 1357 ms 25216 KB
19.txt 880 ms 25088 KB
20.txt 860 ms 24704 KB
21.txt 1029 ms 25216 KB
22.txt 1036 ms 25216 KB
23.txt 3 ms 4352 KB
s1.txt 3 ms 4352 KB
s2.txt 3 ms 4352 KB
s3.txt 3 ms 4352 KB