Submission #1226445

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226445		PenguinsAreCute	Port Facility (JOI17_port_facility)	C++17	0 / 100	0 ms	324 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;
using ii = pair<int,int>;
int main() {
	int n;
	cin >> n;
	vector<int> adj[n];
	pair<int,int> box[n];
	int vis[n];
	memset(vis,0,sizeof(vis));
	for(int i=0;i<n;i++)
		cin >> box[i].first >> box[i].second;
	sort(box,box+n);

	set<ii> connected;
	set<int> rgt;
	for(int i=0;i<n;i++) {
		auto [a, b] = box[i];
		auto itc = connected.lower_bound(ii(b+1,0));
		if(itc != connected.begin()) {
			auto [x, y] = (*--itc);
			auto itc2 = connected.lower_bound(ii(b+1,0));
			if(itc2 == connected.end() || itc2->first > b+1)
				connected.insert({b+1,y});
		}
		connected.insert({b,i});
		rgt.insert(b);
		auto itr = rgt.lower_bound(a);
		int cnt = 0;
		while(1) {
			if(itr == rgt.end() || (*itr) >= b)
				break;
			itc = connected.lower_bound(ii(*itr + 1, 0));
			assert(itc != connected.begin());
			itc--;
			adj[i].push_back(itc->second);
			adj[itc->second].push_back(i);
			if(exchange(cnt,1))
				itc = connected.erase(itc);
			else
				itc++;
			if(itc == connected.end())
				break;
			itr = rgt.lower_bound(itc->first);
		}
	}

	int ans = 1;
	for(int i=0;i<n;i++)
		if(!vis[i]) {
			queue<int> q;
			q.push(i);
			vis[i] = 2;
			ans = (2 * ans) % (1'000'000'007);
			while(q.size()) {
				int x = q.front();
				q.pop();
				for(auto y: adj[x])
					if(!vis[y]) {
						vis[y] = 1 ^ vis[x];
						q.push(y);
					} else if(vis[y] == vis[x])
						ans = 0;
			}
		}
	cout << ans;
}

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