Submission #59898

#	Time	Username	Problem	Language	Result	Execution time	Memory
59898		babo	Port Facility (JOI17_port_facility)	C++14	100 / 100	3577 ms	219716 KiB

port_facility

#include <bits/stdc++.h>
#define L long long
#define mod 1000000007

using namespace std;

struct S{
	L s,e,ord;
}a[1000010];

bool operator<(S a,S b){
	return a.e<b.e;
}

bool cmps(S a,S b){
	return a.s<b.s;
}
bool cmpe(S a,S b){
	return a.e<b.e;
}


L n,ans=1;
L color[1000010];



vector<L>v[1000010];

void dfs(L x){
	L i;
	for(i=0;i<v[x].size();i++)
	{
		if(!color[v[x][i]])
		{
			color[v[x][i]]=3-color[x];
			dfs(v[x][i]);
		}
	}
}

bool ok(){
	L i;
	stack<L>s1,s2;
	for(i=1;i<=n;i++)
	{
		if(color[a[i].ord]==1)
		{
			while(!s1.empty()&&s1.top()<a[i].s) s1.pop();
			if(!s1.empty()&&s1.top()<a[i].e) return 0;
			s1.push(a[i].e);
		}
		else
		{
			while(!s2.empty()&&s2.top()<a[i].s) s2.pop();
			if(!s2.empty()&&s2.top()<a[i].e) return 0;
			s2.push(a[i].e);
		}
	}
	return 1;
}

int main()
{
	scanf("%lld",&n);
	L i;
	for(i=1;i<=n;i++)
	{
		scanf("%lld %lld",&a[i].s,&a[i].e);
		a[i].ord=i;
	}
	sort(a+1,a+n+1,cmps);
	set<S>st;
	for(i=1;i<=n;i++)
	{
		set<S>::iterator it=st.lower_bound((S){a[i].e,a[i].s});
		while(it!=st.end()&&it->e<a[i].e)
		{
			v[a[i].ord].push_back(it->ord);
			v[it->ord].push_back(a[i].ord);
			st.erase(it);
			it=st.lower_bound((S){a[i].e,a[i].s});
		}
		st.insert(a[i]);
	}
	while(!st.empty())
	{
		st.erase(st.begin());
	}
	
	
	for(i=1;i<=n;i++)
	{
		a[i].e*=-1;
		a[i].s*=-1;
		swap(a[i].s,a[i].e);
	}
	
	sort(a+1,a+n+1,cmps);
	
	while(!st.empty())
	{
		st.erase(st.begin());
	}
	for(i=1;i<=n;i++)
	{
		set<S>::iterator it=st.lower_bound((S){a[i].e,a[i].s});
		while(it!=st.end()&&it->e<a[i].e)
		{
			v[a[i].ord].push_back(it->ord);
			v[it->ord].push_back(a[i].ord);
			st.erase(it);
			it=st.lower_bound((S){a[i].e,a[i].s});
		}
		st.insert(a[i]);
	}
	
	
	
	for(i=1;i<=n;i++)
	{
		a[i].e*=-1;
		a[i].s*=-1;
		swap(a[i].s,a[i].e);
	}
	
	sort(a+1,a+n+1,cmps);
	
	for(i=1;i<=n;i++)
	{
		if(!color[i])
		{
			ans*=2;
			ans%=mod;
			color[i]=1;
			dfs(i);
		}
		//printf("%lld ",color[i]);
	}
	if(!ok()) printf("%lld",0);
	else printf("%lld",ans);
}

Compilation message (stderr)

port_facility.cpp: In function 'void dfs(long long int)':
port_facility.cpp:32:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<v[x].size();i++)
          ~^~~~~~~~~~~~
port_facility.cpp: In function 'int main()':
port_facility.cpp:140:27: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int' [-Wformat=]
  if(!ok()) printf("%lld",0);
                           ^
port_facility.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&n);
  ~~~~~^~~~~~~~~~~
port_facility.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld",&a[i].s,&a[i].e);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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