Submission #71453

#	Time	Username	Problem	Language	Result	Execution time	Memory
71453		Pajaraja	Port Facility (JOI17_port_facility)	C++17	100 / 100	5717 ms	216920 KiB

port_facility

#include <bits/stdc++.h>
#define MAXN 1000007
#define MOD 1000000007
using namespace std;
pair<int,int> seg[8*MAXN];
int a[2][MAXN],c[2*MAXN],n;
bool vi[MAXN];
void upd(int l,int r,int v1,int v2,int p,int ind)
{
	if(l==r)
	{
		seg[ind]=make_pair(v1,v2);
		return;
	}
	int s=(l+r)/2;
	if(p<=s) upd(l,s,v1,v2,p,2*ind);
	else upd(s+1,r,v1,v2,p,2*ind+1);
	seg[ind]=make_pair(max(seg[2*ind].first,seg[2*ind+1].first),min(seg[2*ind].second,seg[2*ind+1].second));
}
pair<int,int> nm(int l,int r,int lt ,int rt,int ind)
{
	if(l>rt || r<lt) return make_pair(0,2*MAXN);
	if(l>=lt && r<=rt) return seg[ind];
	int s=(l+r)/2;
	pair<int,int> x=nm(l,s,lt,rt,2*ind),y=nm(s+1,r,lt,rt,2*ind+1);
	return make_pair(max(x.first,y.first),min(x.second,y.second));
}
vector<int> g[MAXN],w,b;
void dfs(int s,int x)
{
	vi[s]=true;
	if(x==1) w.push_back(s);
	else b.push_back(s);
	for(int i=0;i<g[s].size();i++) if(!vi[g[s][i]]) dfs(g[s][i],1-x);
}
bool puca(vector<int> v)
{
	bool pr=false;
	for(int i=0;i<v.size();i++) upd(1,2*n,a[0][v[i]],a[0][v[i]],a[1][v[i]],1);
	for(int i=0;i<v.size();i++)
	{
		pair<int,int> pi=nm(1,2*n,a[0][v[i]],a[1][v[i]],1);
		if(pi.second<a[0][v[i]]) pr=true;
	}
	for(int i=0;i<v.size();i++) upd(1,2*n,0,2*MAXN,a[1][v[i]],1);
	return pr;
}
int main()
{
	int sk=1;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d%d",&a[0][i],&a[1][i]);
		c[a[0][i]]=c[a[1][i]]=i;
		upd(1,2*n,a[0][i],a[0][i],a[1][i],1);
		upd(1,2*n,a[1][i],a[1][i],a[0][i],1);
	}
	for(int i=0;i<n;i++)
	{
		pair<int,int> pi=nm(1,2*n,a[0][i],a[1][i],1);
		if(pi.first>a[1][i])
		{
			g[i].push_back(c[pi.first]);
			g[c[pi.first]].push_back(i);
		}
		if(pi.second<a[0][i])
		{
			g[i].push_back(c[pi.second]);
			g[c[pi.second]].push_back(i);
		}
	}
	for(int i=0;i<2*n;i++) upd(1,2*n,0,2*MAXN,i,1);
	for(int i=0;i<n;i++) if(!vi[i])
	{
		dfs(i,0);
		if(!puca(b) && !puca(w)) sk=(sk*2)%MOD;
		else sk=0;
		b.clear();
		w.clear();
	}
	printf("%d",sk);
}

Compilation message (stderr)

port_facility.cpp: In function 'void dfs(int, int)':
port_facility.cpp:34:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++) if(!vi[g[s][i]]) dfs(g[s][i],1-x);
              ~^~~~~~~~~~~~
port_facility.cpp: In function 'bool puca(std::vector<int>)':
port_facility.cpp:39:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v.size();i++) upd(1,2*n,a[0][v[i]],a[0][v[i]],a[1][v[i]],1);
              ~^~~~~~~~~
port_facility.cpp:40:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v.size();i++)
              ~^~~~~~~~~
port_facility.cpp:45:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v.size();i++) upd(1,2*n,0,2*MAXN,a[1][v[i]],1);
              ~^~~~~~~~~
port_facility.cpp: In function 'int main()':
port_facility.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
port_facility.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&a[0][i],&a[1][i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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