Submission #328436

#	Time	Username	Problem	Language	Result	Execution time	Memory
328436		shivensinha4	Port Facility (JOI17_port_facility)	C++17	0 / 100	1 ms	364 KiB

port_facility

#include "bits/stdc++.h"
using namespace std; 
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
// #define endl '\n'

const ll mod = 1e9+7;

ll modpow(ll a, ll b) {
	ll res = 1;
	while (b) {
		if (b & 1) res = (res * a) % mod;
		a = (a * a) % mod;
		b >>= 1;
	}
	return res;
}

class UFDS {
	public:
	vi p, rank, sz; int count = 0;
	vector<ii> ends;

	UFDS(vector<ii> &nums) {
		int n = nums.size();
		p.resize(n); rank.resize(n); sz.resize(n, 1); ends.resize(n);
		for_(i, 0, n) {
			p[i] = i;
			ends[i] = {nums[i].second, -1};
		}
		count = n;
	}
	int getParent(int i) {
		return (p[i] == i) ? i : (p[i] = getParent(p[i]));
	}
	void join(int i, int j) {
		int a = getParent(i), b = getParent(j);
		// cout << "joining " << a << " " << b << endl;
		if (a == b) return;
		vi vals = {ends[a].first, ends[a].second, ends[b].first, ends[b].second};
		sort(vals.begin(), vals.end(), greater<int>());
		count -= 1;
		if (rank[a] > rank[b]) {
			p[b] = a;
		} else {
			p[a] = b;
			if (rank[a] == rank[b]) rank[b] += 1;
		}
		ends[p[a]] = {vals[0], vals[1]};
	}
};

// const int INF = 1e9;

int main() {
	#ifdef shiven
	freopen("test.in", "r", stdin);
	#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n; cin >> n;
	vector<ii> nums(n);
	for_(i, 0, n) cin >> nums[i].first >> nums[i].second;
	sort(nums.begin(), nums.end());
	
	
	bool valid = true;
	UFDS ufds(nums);
	set<ii> s; // {end pt, idx}
	for_(i, 0, n) {
		int lastComp = -1;
		if (s.size()) {
			auto pta = s.lower_bound({nums[i].first, 0}), ptb = s.lower_bound({nums[i].second, 0});
			
			if (ptb != s.begin()) ptb--;
			
			if ((*ptb).first > nums[i].first and (*ptb).first < nums[i].second) lastComp = (*ptb).second;
			
			// cout << i << " joins element with end " << (*ptb).first << " (" << (*ptb).second << ")" << endl;
			
			auto ptc = pta == s.end() ? pta : next(pta);
			bool first = true;
			
			while ((*pta).first < (*ptb).first) {
				if (first and ufds.ends[ufds.getParent((*pta).second)].second > nums[i].first) {
					valid = false;
					// cout << "stopping because of ends " << ufds.ends[ufds.getParent((*pta).second)].second << " and " << ufds.ends[ufds.getParent((*pta).second)].first << " being in same component "  << endl;
					
				}
				else if (ufds.ends[ufds.getParent((*ptc).second)].second > nums[i].first) {
					// cout << "stopping because of ends " << ufds.ends[ufds.getParent((*ptc).second)].second << " and " << ufds.ends[ufds.getParent((*ptc).second)].first << " being in same component "  << endl;
					
					valid = false;
				}
				
				if (!valid) {
					break;
				}
				
				ufds.join((*pta).second, (*ptc).second);
				s.erase(pta);
				pta = ptc;
				ptc = next(ptc);
				first = false;
			}
		}
		
		if (!valid) break;
		
		s.insert({nums[i].second, i});
		if (lastComp != -1) ufds.join(lastComp, i);
	}
	
	if (valid) cout << modpow(2, ufds.count);
	else cout << 0;
	cout << endl;

	return 0;
}

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