Submission #27812

#	Time	Username	Problem	Language	Result	Execution time	Memory
27812		khsoo01	Port Facility (JOI17_port_facility)	C++11	100 / 100	2379 ms	114752 KiB

port_facility

#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef pair<int, int> pii;
const int N = 1000005, mod = 1e9+7;
int n;
bool vis[N];

vector<int> st;
set<pii> s;

struct gugan {
	int s, e;
	bool operator < (const gugan &T) const {
		return e > T.e;
	}
} g[N];
vector<gugan> res[2];

int mgi (int A, int B) {
	if(A == -1) return B;
	if(B == -1) return A;
	return g[A].s < g[B].s ? A : B;
}

struct disj {
	int fr[N], op[N];
	void init () {
		for(int i=1;i<=n;i++) {
			fr[i] = i; op[i] = -1;
		}
	}
	int ff (int P) {
		if(fr[P] == P) return P;
		return fr[P] = ff(fr[P]);
	}
	int fo (int P) {
		if(op[P] == -1) return -1;
		return op[P] = ff(op[P]);
	}
	void Union (int A, int B) {
		A = ff(A); B = ff(B);
		if(op[A] == -1) op[A] = B;
		if(op[B] == -1) op[B] = A;
		op[A] = fo(A); op[B] = fo(B);
		int P = mgi(A, op[B]), Q = mgi(B, op[A]);
		fr[A] = P; fr[op[B]] = P;
		fr[B] = Q; fr[op[A]] = Q;
		op[P] = Q; op[Q] = P;
	}
} uf;

vector<pii> ev;

bool can (vector<gugan> &V) {
	ev.clear(); st.clear();
	for(int i=0;i<V.size();i++) {
		ev.push_back(pii(V[i].s, i+1));
		ev.push_back(pii(V[i].e, -i-1));
	}
	sort(ev.begin(), ev.end());
	for(int i=0;i<ev.size();i++) {
		int T = ev[i].Y;
		if(T < 0) {
			if(st.back() != -T) return false;
			st.pop_back();
		}
		else st.push_back(T);
	}
	return true;
}

int main()
{
	scanf("%d",&n); uf.init();
	for(int i=1;i<=n;i++) {
		scanf("%d%d",&g[i].s,&g[i].e);
	}
	sort(g+1, g+1+n);
	for(int i=1;i<=n;i++) {
		while(!st.empty() && g[i].e < g[st.back()].s) {
			st.pop_back();
		}
		auto it = s.lower_bound(pii(g[i].s, 0));
		if(it != s.end() && (it->X) <= g[i].e) {
			int V = uf.ff(it->Y);
			while(!st.empty()) {
				int T = st.back(); st.pop_back();
				if(uf.ff(T) == V || uf.fo(T) == V) break;
				uf.Union(T, i);
			}
			uf.Union(V, i);
		}
		int A = uf.ff(i), B = uf.fo(i);
		st.push_back(mgi(A, B));
		s.insert(pii(g[i].s, i));
	}
	int ans = 1;
	for(int i=1;i<=n;i++) {
		if(uf.ff(i) == i && !vis[i]) {
			ans = (ans * 2) % mod;
			if(~uf.op[i]) vis[uf.fo(i)] = true;
		}
	}
	for(int i=1;i<=n;i++) {
		res[vis[uf.ff(i)]].push_back(g[i]);
	}
	if(!can(res[0]) || !can(res[1])) puts("0");
	else printf("%d\n",ans);
}

Compilation message (stderr)

port_facility.cpp: In function 'bool can(std::vector<gugan>&)':
port_facility.cpp:58:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<V.size();i++) {
               ^
port_facility.cpp:63:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<ev.size();i++) {
               ^
port_facility.cpp: In function 'int main()':
port_facility.cpp:76:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n); uf.init();
                ^
port_facility.cpp:78:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&g[i].s,&g[i].e);
                                ^

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