Submission #447366

#	Time	Username	Problem	Language	Result	Execution time	Memory
447366		alan8585	Port Facility (JOI17_port_facility)	C++14	78 / 100	6107 ms	336748 KiB

port_facility

#pragma GCC optimize ("Ofast","unroll-loops")
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define MP make_pair
#define F first
#define S second
#define setpre(a) cout.precision(a),cout<<fixed;
#define ALL(a) a.begin(),a.end()
#define MEM(a,b) memset(a,b,sizeof a)
#define Tie ios::sync_with_stdio(0),cin.tie(0);
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;

struct datas {
	int x, y;
	bool operator<(const datas &a) const {
		return x < a.x;
	}
};

vector<datas> ori;
vector<int> e[1000100];
int n, v[1000100], tv[1000100], sz[2000100], C[2000100];

inline int find(int a) {
	return C[a] != a ? C[a] = find(C[a]) : a;
}

inline int max(int a, int b) {
	return a < b ? b : a;
}

inline void swap(int &a, int &b) {
	a ^= b, b ^= a, a ^= b;
}

inline void merge(int a, int b) {
	(a = find(a)) != (b = find(b)) && (sz[a] < sz[b] && (swap(a, b), 1), sz[a] += sz[b], C[b] = a);
}

void merge_sort(int l, int r) {
	if (l == r)
		return;
	int m = l+r >> 1, tl = l, tr = m + 1, now = -1;
	merge_sort(l, m), merge_sort(m + 1, r);
	for (int i = l; i <= r; ++i)
		tr > r || (tl <= m && ori[v[tl]].y < ori[v[tr]].y) ? (now == -1 || ori[now].y < ori[v[tl]].y) && (now = v[tl]), tv[i] = v[tl++] : (now != -1 && ori[v[tr]].x < ori[now].y && (e[v[tr]].pb(now), e[now].pb(v[tr]), merge(v[tr], now + n), merge(now, v[tr] + n), 1), tv[i] = v[tr++]);
	// for(int i = l; i <= r; i++)
	//     v[i] = tv[i];
	memcpy(v + l, tv + l, sizeof(int) * (r - l + 1));
}

int vis[1000100];
vector<int> lv, rv;
inline void dfs(int a, int c) {
	++vis[a], (c ? rv : lv).pb(a);
	for(int i : e[a])
		vis[i] || (dfs(i, ~c), 0);
}

inline bool f(int a, int b) {
	return ori[a].x < ori[b].x;
}

int main() {
	Tie
	cin >> n;
	ori.resize(n);
	for(int i = 0; i < n; ++i)
		cin >> ori[i].x >> ori[i].y;
	for(int i = 0; i < (n<<1); ++i)
		C[i] = i, sz[i] = 1;

	for(int i = 0; i < n; ++i)
		v[i] = i;	
	sort(v, v + n, f), merge_sort(0, n - 1);

	for (int i = 0; i < n; ++i)
		ori[i].x = (n<<1|1) - ori[i].x, ori[i].y = (n<<1|1) - ori[i].y, swap(ori[i].x, ori[i].y);

	for (int i = 0; i < n; ++i)
		v[i] = i;
	sort(v, v + n, f), merge_sort(0, n - 1);

	int ans = 1;
	for (int i = 0; i < n; ++i) {
		if (!vis[i]) {
			lv.clear(), rv.clear(), dfs(i, 0);
	
			sort(ALL(lv), f);
			int mx = -1;
			for (int j : lv) {
				if(ori[j].x < mx && mx < ori[j].y) {
					cout << "0\n";
					return 0;
				}
				mx = max(mx, ori[j].y);
			}
	
			sort(ALL(rv), f);
			mx = -1;
			for (int j : rv) {
				if (ori[j].x < mx && mx < ori[j].y) {
					cout << "0\n";
					return 0;
				}
				mx = max(mx, ori[j].y);
			}
		}
	}
	for (int i = 0; i < n; ++i)
		if (find(i) == find(i + n)) {
			cout << "0\n";
			return 0;
		}
	int tmp = 0;
	for (int i = 0; i < (n<<1); ++i)
		find(i) == i && ++tmp;
	tmp >>= 1;
	for(int i = 0; i < tmp; ++i)
		ans <<= 1, ans %= 1000000007;
	cout << ans << '\n';
}

Compilation message (stderr)

port_facility.cpp: In function 'void merge(int, int)':
port_facility.cpp:43:92: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   43 |  (a = find(a)) != (b = find(b)) && (sz[a] < sz[b] && (swap(a, b), 1), sz[a] += sz[b], C[b] = a);
      |                                                                                       ~~~~~^~~
port_facility.cpp: In function 'void merge_sort(int, int)':
port_facility.cpp:49:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |  int m = l+r >> 1, tl = l, tr = m + 1, now = -1;
      |          ~^~

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 56 / 56
• Subtask 4: 0 / 22