Submission #338806

#	Time	Username	Problem	Language	Result	Execution time	Memory
338806		wwdd	Port Facility (JOI17_port_facility)	C++14	0 / 100	1 ms	384 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:
		vi rk,p;
		int n,nc;
	public:
		U(int n_) {
			n = n_;
			rk.assign(n,0);
			nc = n;
			for(int i=0;i<n;i++) {
				p.push_back(i);
			}
		}
		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) {
			if(same(a,b)) {return false;}
			int x = find(a),y = find(b);
			if(rk[x] < rk[y]) {swap(x,y);}
			if(rk[x] == rk[y]) {rk[x]++;}
			p[y] = x;
			nc--;
			return true;
		}
		int num() {
			return nc;
		}
};
int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	int n;
	cin >> n;
	U bs(n);
	vector<ii> st,dt;
	vector<ii> su,bu;
	vector<ii> w;
	ll res = 1;
	for(int i=0;i<n;i++) {
		int a,b;
		cin >> a >> b;
		w.emplace_back(a,b);
	}
	sort(w.begin(),w.end());
	for(int i=0;i<w.size();i++) {
		ii va = w[i];
		while(!dt.empty() && dt.back().second < va.first) {
			dt.pop_back();
			bu.back().second--;
			if(bu.back().second == 0) {bu.pop_back();}
		}
		while(!st.empty() && st.back().second < va.first) {
			st.pop_back();
			su.back().second--;
			if(su.back().second == 0) {su.pop_back();}
		}
		if(st.empty() || va.second < st.back().second) {
			st.push_back(va);
			int bo = 0;
			while(!bu.empty() && va.second > dt[dt.size()-bo-1].second) {
				bs.un(i,bu.back().first);
				bo += bu.back().second;
				bu.pop_back();
			}
			su.push_back({i,1});
			if(bo > 0) {
				bu.push_back({i,bo});
			}
		} else {
			if(bu.empty() || va.second < dt.back().second) {
				int bo = 0;
				while(!su.empty() && va.second > st[st.size()-bo-1].second) {
					bs.un(i,su.back().first);
					bo += su.back().second;
					su.pop_back();
				}
				if(bo > 0) {
					su.push_back({i,bo});
				}
				dt.push_back(va);
				bu.push_back({i,1});
			} else {
				res = 0;
				break;
			}
		}
	}
	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:53: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]
   53 |  for(int i=0;i<w.size();i++) {
      |              ~^~~~~~~~~

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