Submission #338879

#	Time	Username	Problem	Language	Result	Execution time	Memory
338879		wwdd	Port Facility (JOI17_port_facility)	C++14	100 / 100	1606 ms	226244 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
const ll M = 1e9+7;
class U {
	private:
		vector<set<int>> cont[2];
		vi p,sz;
		int n,nc;
	public:
		U(vector<ii> w) {
			n = w.size();
			cont[0].assign(n,set<int>());
			cont[1].assign(n,set<int>());
			nc = n;
			sz.assign(n,1);
			for(int i=0;i<n;i++) {
				p.push_back(i);
				cont[0][i].insert(w[i].second);
			}
		}
		int find(int a) {
			if(a == p[a]) {return a;}
			return p[a] = find(p[a]);
		}
		bool same(int a, int b) {return find(a) == find(b);}
		bool un(int a, int b, int u, int v) {
			if(same(a,b)) {return false;}
			int x = find(a),y = find(b);
			int par = (cont[0][x].count(u))^(cont[1][y].count(v));
			if(sz[x] < sz[y]) {swap(x,y);}
			for(int i=0;i<2;i++) {
				cont[i][x].insert(cont[i^par][y].begin(),cont[i^par][y].end());
				cont[i^par][y].clear();
			}
			p[y] = x;
			sz[x] += sz[y];
			nc--;
			return true;
		}
		int num() {
			return nc;
		}
		ii pop(int u) {
			u = find(u);
			int res[2] = {1<<29,1<<29};
			for(int i=0;i<2;i++) {
				if(cont[i][u].size() > 0) {
					res[i] = *cont[i][u].begin();
				}
			}
			int idx = res[0] > res[1];
			if(cont[idx][u].size() > 0) {
				cont[idx][u].erase(cont[idx][u].begin());
				res[idx] = (cont[idx][u].size() > 0?*cont[idx][u].begin():1<<29);
			}
			return {res[0],res[1]};
		}
		ll dup(int u) {
			u = find(u);
			int res = -1e9;
			for(int i=0;i<2;i++) {
				if(cont[i][u].empty()) {
					return 1e9;
				}
				res = max(res,*cont[i][u].begin());
			}
			return res;
		}
};
int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	int n;
	cin >> n;
	vector<ii> w;
	vi rm(2*n,-1);
	for(int i=0;i<n;i++) {
		int a,b;
		cin >> a >> b;
		a--;b--;
		w.emplace_back(a,b);
	}
	sort(w.begin(),w.end());
	for(int i=0;i<n;i++) {
		rm[w[i].first] = rm[w[i].second] = i;
	}
	U bs(w);
	map<int,int> lu;
	int rop = 0;
	ll res = 1;
	for(int i=0;i<w.size();i++) {
		ii va = w[i];
		while(!lu.empty() && lu.begin()->first < va.first) {
			int id = bs.find(lu.begin()->second);
			lu.erase(lu.begin());
			ii nx = {-1,-1};
			while(min(nx.first,nx.second) < va.first) {
				nx = bs.pop(id);
			}
			int bu[2] = {nx.first,nx.second};
			lu[min(nx.first,nx.second)] = id;
		}
		if(!lu.empty() && lu.begin()->first < va.second) {
			ll mv = lu.begin()->first;
			while(!lu.empty() && lu.begin()->first < va.second) {
				ll ko = lu.begin()->second;
				ll kv = lu.begin()->first;
				if(bs.dup(ko) < va.second) {
					res = 0;
				}
				bs.un(ko,i,kv,va.second);
				lu.erase(lu.begin());
			}
			lu[mv] = i;
		} else {
			lu[va.second] = i;
		}
	}
	ll lol = bs.num();
	for(int i=0;i<lol;i++) {
		res *= 2;
		if(res >= M) {res -= M;}
	}
	cout << res << '\n';
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:93:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |  for(int i=0;i<w.size();i++) {
      |              ~^~~~~~~~~
port_facility.cpp:102:8: warning: unused variable 'bu' [-Wunused-variable]
  102 |    int bu[2] = {nx.first,nx.second};
      |        ^~
port_facility.cpp:91:6: warning: unused variable 'rop' [-Wunused-variable]
   91 |  int rop = 0;
      |      ^~~

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