Submission #7021466

---

Source Code Expand

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<sstream>
#include<complex>
#include<functional>
#include<vector>
#include<map>
#include<queue>
#include<deque>
#include<stack>
#include<set>

using namespace std;
#define endl '\n'

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;

template<typename T = long long>
T gcd(T a, T b) { return b ? gcd(b, a%b) : a; }

// value

//-----------------------コピペここから--------------------------

/* 拡張ユークリッドの互除法(ax + by = 1 を満たすx, y) */
template<typename T>
T extgcd(T a, T b, T& x, T& y) {
	T d = a;
	if (b != 0) {
		d = extgcd(b, a % b, y, x);
		y -= (a / b) * x;
	}
	else {
		x = 1; y = 0;
	}
	return d;
}

/* MODを法とする環 */
template<typename T, T MOD = 998244353>
struct Mint {

	static constexpr T mod = MOD;

	T v;

	/* コンストラクタ群 */
	Mint() :v(0) {}

	Mint(signed _v) :v(_v) {}

	Mint(long long t) {
		v = t % mod;
		if (v < 0) v += mod;
	}

	/* べき乗を計算 */
	Mint pow(long long k) {
		Mint res(1), tmp(v);
		while (k) {
			if (k & 1) res *= tmp;
			tmp *= tmp;
			k >>= 1;
		}
		return res;
	}

	/* 単位元 */
	static Mint add_identity() { return Mint(0); }
	static Mint mul_identyty() { return Mint(1); }

	/* 逆元を求める */
	// オイラーの定理
	Mint inv() { return pow(mod - 2); }

	// 拡張ユークリッド互除法
	Mint inv_euclid() {
		T x, y;
		extgcd(v, mod, x, y);
		return Mint(x);
	}

	/* 演算子群 */
	Mint& operator+=(Mint a) {
		v += a.v;
		if (v >= mod) v -= mod;
		return *this;
	}

	Mint& operator-=(Mint a) {
		v += mod - a.v;
		if (v >= mod) v -= mod;
		return *this;
	}

	Mint& operator*=(Mint a) {
		v = 1LL * v * a.v % mod;
		return *this;
	}

	Mint& operator/=(Mint a) {
		return (*this) *= a.inv();
		// ユークリッドの互除法を使う場合
		// return (*this) *= a.inv_euclid();
	}

	Mint& operator+=(T a) { return (*this) += Mint(a); }
	Mint& operator-=(T a) { return (*this) -= Mint(a); }
	Mint& operator*=(T a) { return (*this) *= Mint(a); }
	Mint& operator/=(T a) { return (*this) /= Mint(a); }

	Mint operator+(Mint a) const { return Mint(v) += a; }
	Mint operator-(Mint a) const { return Mint(v) -= a; }
	Mint operator*(Mint a) const { return Mint(v) *= a; }
	Mint operator/(Mint a) const { return Mint(v) /= a; }

	Mint operator+(T a) const { return Mint(v) += a; }
	Mint operator-(T a) const { return Mint(v) -= a; }
	Mint operator*(T a) const { return Mint(v) *= a; }
	Mint operator/(T a) const { return Mint(v) /= a; }

	Mint operator-() const { return v ? Mint(mod - v) : Mint(v); }

	bool operator==(const Mint a) const { return v == a.v; }

	bool operator!=(const Mint a) const { return v != a.v; }

	bool operator<(const Mint a) const { return v < a.v; }

	bool operator>(const Mint a) const { return v > a.v; }

	/* 組み合わせ */
	static Mint comb(long long n, int k) {
		Mint num(1), dom(1);
		for (int i = 0; i < k; i++) {
			num *= Mint(n - i);
			dom *= Mint(i + 1);
		}
		return num / dom;
	}

};

template<typename T, T MOD> constexpr T Mint<T, MOD>::mod;

/* ostreamで出力できるように */
template<typename T, T MOD>
ostream& operator<<(ostream &os, Mint<T, MOD> m) { os << m.v; return os; }

//-----------------------コピペここまで--------------------------

struct BIT {

	int size;
	vector<Mint<ll>> data;

	BIT(int n) : size(n), data(n + 2) {
	}

	Mint<ll> sum(int i) {
		Mint<ll> ret = 0;
		while (i > 0) {
			ret += data[i];
			i -= i & -i;
		}
		return ret;
	}

	void add(int i, int x) {
		while (i <= size) {
			data[i] += x;
			i += i & -i;
		}
	}

};

int N;
pair<int, int> node[200020];
Mint<ll> a[200020], c[200020], d[200020], b[200020];

bool compare_by_b(pair<int, int> a, pair<int, int> b) {
	if (a.second != b.second) {
		return a.second < b.second;
	}
	else {
		return a.first < b.first;
	}
}

void solve() {

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> node[i].first >> node[i].second;
	}

	sort(node, node + N, compare_by_b);
	for (int i = 0, num = 1, tmp = node[0].second; i < N; i++) {
		if (tmp != node[i].second) num++;
		tmp = node[i].second;
		node[i].second = num;
	}

	sort(node, node + N);

	BIT left(N), right(N);

	for (int i = 0; i < N; i++) {
		left.add(node[i].second, 1);
		a[i] = left.sum(node[i].second) - 1;
		c[i] = Mint<ll>(i) - a[i];
	}

	for (int i = 0; i < N; i++) {
		right.add(node[N - 1 - i].second, 1);
		b[N - 1 - i] = right.sum(node[N - 1 - i].second) - 1;
		d[N - 1 - i] = Mint<ll>(i) - d[N - 1 - i];
	}

	Mint<ll> ans = 0;
	Mint<ll> two = 2;
	for (int i = 0; i < N; i++) {
		ans += (two.pow(a[i].v) - 1) * (two.pow(b[i].v) - 1) * two.pow((c[i] + d[i]).v);
		ans += (two.pow(c[i].v) - 1) * (two.pow(d[i].v) - 1) * two.pow((a[i] + b[i]).v);
		ans -= (two.pow(a[i].v) - 1) * (two.pow(b[i].v) - 1) * (two.pow(c[i].v) - 1) * (two.pow(d[i].v) - 1);
		ans += two.pow((a[i] + b[i] + c[i] + d[i]).v);
	}

	cout << ans << endl;

	return;

}

int main() {

	cin.tie(0);
	ios::sync_with_stdio(false);

	solve();

	return 0;

}

Submission Info

Judge Result