Submission #6700993

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define MOD 998244353

int n, po[200005], x[200005], y[200005], za[800005], zb[800005], ans;
pair<int, int> pa[200005], pb[200005];

void add(int& a, int b) {
	a += b;
	if (a >= MOD)
		a -= MOD;
}

void build(int l, int r, int i) {
	if (l + 1 == r) {
		zb[i] = 1;
		return;
	}
	int mi = (l + r) / 2;
	build(l, mi, i * 2);
	build(mi, r, i * 2 + 1);
	zb[i] = zb[i * 2] + zb[i * 2 + 1];
}

void f1(int a, int l, int r, int i) {
	za[i]++;
	if (a == l && a + 1 == r)
		return;
	int mi = (l + r) / 2;
	if (a < mi)
		f1(a, l, mi, i * 2);
	else
		f1(a, mi, r, i * 2 + 1);
}

void f2(int a, int l, int r, int i) {
	zb[i]--;
	if (a == l && a + 1 == r)
		return;
	int mi = (l + r) / 2;
	if (a < mi)
		f2(a, l, mi, i * 2);
	else
		f2(a, mi, r, i * 2 + 1);
}

int qa(int a, int b, int l, int r, int i) {
	if (a == l && b == r)
		return za[i];
	int mi = (l + r) / 2, re = 0;
	if (a < mi)
		re = qa(a, min(mi, b), l, mi, i * 2);
	if (mi < b)
		re += qa(max(mi, a), b, mi, r, i * 2 + 1);
	return re;
}

int qb(int a, int b, int l, int r, int i) {
	if (a == l && b == r)
		return zb[i];
	int mi = (l + r) / 2, re = 0;
	if (a < mi)
		re = qb(a, min(mi, b), l, mi, i * 2);
	if (mi < b)
		re += qb(max(mi, a), b, mi, r, i * 2 + 1);
	return re;
}

int main() {
	po[0] = 1;
	for (int i = 1; i < 200005; i++) {
		po[i] = po[i - 1];
		add(po[i], po[i]);
	}
	for (int i = 0; i < 200005; i++)
		po[i]--;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d%d", &pa[i].first, &pb[i].first);
		pa[i].second = pb[i].second = i;
	}
	sort(pa, pa + n);
	for (int i = 0; i < n; i++)
		x[pa[i].second] = i;
	sort(pb, pb + n);
	ans = (long long)po[n] * n % MOD;
	build(0, n, 1);
	// printf("%d\n", ans);
	for (int i = 0; i < n; i++) {
		int id = pb[i].second;
		f2(x[id], 0, n, 1);
		// printf("%d %d %d %d\n", i, n - i - 1, x[id], n - x[id] - 1);
		add(ans, MOD - po[i]);
		add(ans, MOD - po[n - i - 1]);
		add(ans, MOD - po[x[id]]);
		add(ans, MOD - po[n - x[id] - 1]);
		if (x[id]) {
			// printf("A %d %d\n", qa(0, x[id], 0, n, 1), qb(0, x[id], 0, n, 1));
			add(ans, po[qa(0, x[id], 0, n, 1)]);
			add(ans, po[qb(0, x[id], 0, n, 1)]);
		}
		if (x[id] + 1 != n) {
			// printf("B %d %d\n", qa(x[id] + 1, n, 0, n, 1), qb(x[id] + 1, n, 0, n, 1));
			add(ans, po[qa(x[id] + 1, n, 0, n, 1)]);
			add(ans, po[qb(x[id] + 1, n, 0, n, 1)]);
		}
		f1(x[id], 0, n, 1);
	}
	printf("%d\n", ans);
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:79:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
./Main.cpp:81:44: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &pa[i].first, &pb[i].first);
                                            ^

Judge Result