Submission #533859

#	Time	Username	Problem	Language	Result	Execution time	Memory
533859		sare	Port Facility (JOI17_port_facility)	C++17	22 / 100	6079 ms	18936 KiB

port_facility

//In the name of Allah :)
#include <bits/stdc++.h>
using namespace std;
string to_string(char c) { return string(1,c); }
string to_string(bool b) { return b ? "true" : "false"; }
string to_string(const char* s) { return (string)s; }
string to_string(string s) { return s; }
template<class A> string to_string(complex<A> c) { 
	stringstream ss; ss << c; return ss.str(); }
string to_string(vector<bool> v) { 
	string res = "{"; for(int i = 0; i < (int)v.size(); i++) res += char('0'+v[i]);
	res += "}"; return res; }
template<size_t SZ> string to_string(bitset<SZ> b) {
	string res = ""; for(size_t i = 0; i < SZ; i++) res += char('0'+b[i]);
	return res; }
template<class A, class B> string to_string(pair<A,B> p);
template<class T> string to_string(T v) { // containers with begin(), end()
	bool fst = 1; string res = "{";
	for (const auto& x: v) {
		if (!fst) res += ", ";
		fst = 0; res += to_string(x);
	}
	res += "}"; return res;
}
template<class A, class B> string to_string(pair<A,B> p) {
	return "("+to_string(p.first)+", "+to_string(p.second)+")"; }
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
	cerr << to_string(h); if (sizeof...(t)) cerr << ", ";
	DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL
#define wis(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "] : [", DBG(__VA_ARGS__)
#else
#define wis(...) 0
#endif
typedef long long ll;
#define all(x) (x).begin(), (x).end()
const int MAXN = 1e5 + 10, MOD = 1e9 + 7;
vector<int> adj[MAXN];
pair<int, int> a[MAXN];
bitset<MAXN> mark;
int color[MAXN];
bool bip = 1;

void dfs (int v, int c) {
	mark[v] = 1;
	color[v] = c;
	for (int i : adj[v]) {
		if (mark[i]) {
			bip &= color[i] != c;
		}
		else {
			dfs(i, c ^ 1);
		}
	}
}
 
int main() {
	ios::sync_with_stdio(0);
#ifndef LOCAL
	cin.tie(0);
#endif
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i].first >> a[i].second;
	}
	sort(a, a + n);
	for (int j = 0; j < n; j++) {
		for (int i = j + 1; i < n; i++) {
			if (a[i].first < a[j].second && a[i].second > a[j].second) {
				adj[i].push_back(j);
				adj[j].push_back(i);
			}
			if (a[i].first > a[j].second) {
				break;
			}
		}
	}

	int m = 0;
	for (int i = 0; i < n; i++) {
		if (!mark[i]) {
			dfs(i, 0);
			m++;
		}
	}
	if (bip == 0) {
		cout << 0 << '\n';
		return 0;
	}
	int ans = 1;
	while (m--) {
		ans = ans + ans >= MOD ? ans + ans - MOD : ans + ans;
	}
	cout << ans << '\n';
}

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