Submission #6706006


Source Code Expand

Copy
// need
#include <iostream>
#include <algorithm>
// data structure
#include <bitset>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <complex>
//#include <deque>
#include <valarray>
#include <unordered_map>
#include <unordered_set>
#include <array>
// etc
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <chrono>
#include <random>
#include <numeric>

// input
#define INIT std::ios::sync_with_stdio(false);std::cin.tie(0);
#define VAR(type, ...)type __VA_ARGS__;MACRO_VAR_Scan(__VA_ARGS__);
template<typename T> void MACRO_VAR_Scan(T& t) { std::cin >> t; }
template<typename First, typename...Rest>void MACRO_VAR_Scan(First& first, Rest& ...rest) { std::cin >> first; MACRO_VAR_Scan(rest...); }
#define VEC_ROW(type, n, ...)std::vector<type> __VA_ARGS__;MACRO_VEC_ROW_Init(n, __VA_ARGS__); for(int w_=0; w_<n; ++w_){MACRO_VEC_ROW_Scan(w_, __VA_ARGS__);}
template<typename T> void MACRO_VEC_ROW_Init(int n, T& t) { t.resize(n); }
template<typename First, typename...Rest>void MACRO_VEC_ROW_Init(int n, First& first, Rest& ...rest) { first.resize(n); MACRO_VEC_ROW_Init(n, rest...); }
template<typename T> void MACRO_VEC_ROW_Scan(int p, T& t) { std::cin >> t[p]; }
template<typename First, typename...Rest>void MACRO_VEC_ROW_Scan(int p, First& first, Rest& ...rest) { std::cin >> first[p]; MACRO_VEC_ROW_Scan(p, rest...); }
#define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
#define MAT(type, c, m, n) std::vector<std::vector<type>> c(m, std::vector<type>(n));for(auto& R:c)for(auto& w:R)std::cin>>w;
// output
#define OUT(dist) std::cout<<(dist);
#define FOUT(n, dist) std::cout<<std::fixed<<std::setprecision(n)<<(dist);
#define SOUT(n, c, dist) std::cout<<std::setw(n)<<std::setfill(c)<<(dist);
#define SP std::cout<<" ";
#define TAB std::cout<<"\t";
#define BR std::cout<<"\n";
#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define ENDL std::cout<<std::endl;
#define FLUSH std::cout<<std::flush;
#define SHOW(dist) {std::cerr << #dist << "\t:" << (dist) << "\n";}
#define SHOWVECTOR(v) {std::cerr << #v << "\t:";for(const auto& xxx : v){std::cerr << xxx << " ";}std::cerr << "\n";}
#define SHOWVECTOR2(v) {std::cerr << #v << "\t:\n";for(const auto& xxx : v){for(const auto& yyy : xxx){std::cerr << yyy << " ";}std::cerr << "\n";}}
#define SHOWQUEUE(a) {auto tmp(a);std::cerr << #a << "\t:";while(!tmp.empty()){std::cerr << tmp.front() << " ";tmp.pop();}std::cerr << "\n";}
#define SHOWSTACK(a) {auto tmp(a);std::cerr << #a << "\t:";while(!tmp.empty()){std::cerr << tmp.top() << " ";tmp.pop();}std::cerr << "\n";}
// utility
#define ALL(a) (a).begin(),(a).end()
#define FOR(w, a, n) for(int w=(a);w<(n);++w)
#define RFOR(w, a, n) for(int w=(n)-1;w>=(a);--w)
#define REP(w, n) for(int w=0;w<int(n);++w)
#define RREP(w, n) for(int w=int(n)-1;w>=0;--w)
#define IN(a, x, b) (a<=x && x<b)
template<class T> inline T CHMAX(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T CHMIN(T& a, const T b) { return a = (a > b) ? b : a; }
// test
template<class T> using V = std::vector<T>;
template<class T> using VV = V<V<T>>;

template<typename S, typename T>
std::ostream& operator<<(std::ostream& os, std::pair<S, T> p) {
	os << "(" << p.first << ", " << p.second << ")"; return os;
}

#define random_shuffle "USE std::shuffle!";

// type/const
#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using PAIR = std::pair<int, int>;
using PAIRLL = std::pair<ll, ll>;
constexpr int INFINT = (1 << 30) - 1;                    // 1.07x10^ 9
constexpr int INFINT_LIM = (1LL << 31) - 1;              // 2.15x10^ 9
constexpr ll INFLL = 1LL << 60;                          // 1.15x10^18
constexpr ll INFLL_LIM = (1LL << 62) - 1 + (1LL << 62);  // 9.22x10^18
constexpr double EPS = 1e-10;
constexpr int MOD = 998244353;
constexpr double PI = 3.141592653589793238462643383279;
template<class T, size_t N> void FILL(T(&a)[N], const T & val) { for (auto& x : a) x = val; }
template<class ARY, size_t N, size_t M, class T> void FILL(ARY(&a)[N][M], const T & val) { for (auto& b : a) FILL(b, val); }
template<class T> void FILL(std::vector<T> & a, const T & val) { for (auto& x : a) x = val; }
template<class ARY, class T> void FILL(std::vector<std::vector<ARY>> & a, const T & val) { for (auto& b : a) FILL(b, val); }
// ------------>8------------------------------------->8------------

struct BIT {
	int N;
	using TYPE = int;
	std::vector<TYPE> bit;
	BIT() : N(0) {}
	BIT(int n) : N(n), bit(N + 1, 0) {}
	BIT(int n, TYPE init) : N(n), bit(N + 1, init) {}

	// bit[i] += w;
	void add(int i, TYPE w) {
		for (int x = ++i; x <= N; x += x & -x) bit[x] += w;
	}
	// return sum [0, i);
	TYPE sum(int i) {
		TYPE res = 0;
		for (int x = i; x > 0; x -= x & -x) res += bit[x];
		return res;
	}
	// return sum [i, j);
	TYPE sum(int i, int j) {
		return sum(j) - sum(i);
	}
	const TYPE& operator[](const int& i) const {
		return bit[i];
	}
};

int p2[200005];

signed main() {
	INIT;

	VAR(int, n);
	VEC_ROW(int, n, x, y);

	p2[0] = 1;
	REP(i, 200004) p2[i + 1] = p2[i] * 2 % MOD;

	int ans = n * (p2[n] - 1);

	{
		std::map<int, int> map;
		REP(i, n) map[x[i]];
		int t = 0;
		for (auto& p : map) p.second = t++;
		REP(i, n) x[i] = map[x[i]];
	}
	V<int> inv(n);
	{
		std::map<int, int> map;
		REP(i, n) map[y[i]];
		int t = 0;
		for (auto& p : map) p.second = t++;
		REP(i, n) {
			y[i] = map[y[i]];
			inv[y[i]] = i;
		}
	}

	REP(i, n) {
		const int L = x[i];
		const int R = n - 1 - L;
		const int D = y[i];
		const int U = n - 1 - D;

		(ans -= p2[L]) %= MOD;
		(ans -= p2[R]) %= MOD;
		(ans -= p2[D]) %= MOD;
		(ans -= p2[U]) %= MOD;
	}

	{
		BIT bit(n);
		REP(i, n) {
			int id = inv[i];
			(ans += p2[bit.sum(x[id])]) %= MOD;
			(ans += p2[bit.sum(x[id] + 1, n)]) %= MOD;
			bit.add(x[id], 1);
		}
	}
	{
		BIT bit(n);
		RREP(i, n) {
			int id = inv[i];
			(ans += p2[bit.sum(x[id])]) %= MOD;
			(ans += p2[bit.sum(x[id] + 1, n)]) %= MOD;
			bit.add(x[id], 1);
		}
	}
	if (ans < 0) ans += MOD;
	OUT(ans)BR;

	return 0;
}

Submission Info

Submission Time
Task F - Enclosed Points
User satanic0258
Language C++14 (GCC 5.4.1)
Score 600
Code Size 6299 Byte
Status AC
Exec Time 411 ms
Memory 19072 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 26
Set Name Test Cases
Sample s1.txt, s2.txt, s3.txt
All 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 AC 2 ms 1792 KB
02.txt AC 2 ms 1792 KB
03.txt AC 2 ms 1792 KB
04.txt AC 2 ms 1792 KB
05.txt AC 2 ms 1792 KB
06.txt AC 3 ms 1792 KB
07.txt AC 3 ms 1792 KB
08.txt AC 2 ms 1792 KB
09.txt AC 2 ms 1792 KB
10.txt AC 2 ms 1792 KB
11.txt AC 363 ms 18816 KB
12.txt AC 357 ms 18432 KB
13.txt AC 370 ms 18944 KB
14.txt AC 354 ms 18176 KB
15.txt AC 411 ms 19072 KB
16.txt AC 381 ms 19072 KB
17.txt AC 369 ms 19072 KB
18.txt AC 366 ms 19072 KB
19.txt AC 356 ms 18944 KB
20.txt AC 352 ms 18688 KB
21.txt AC 348 ms 19072 KB
22.txt AC 353 ms 19072 KB
23.txt AC 3 ms 1792 KB
s1.txt AC 3 ms 1792 KB
s2.txt AC 2 ms 1792 KB
s3.txt AC 2 ms 1792 KB