Submission #318948

#	Time	Username	Problem	Language	Result	Execution time	Memory
318948		arnold518	Port Facility (JOI17_port_facility)	C++14	100 / 100	2148 ms	408240 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e6;
const ll MOD = 1e9+7;

int N;
pii A[MAXN+10];
vector<int> adj[MAXN+10];

bool flag=true;

vector<int> tree[MAXN*4+10];
vector<int> memo;

void get(int node, int tl, int tr, int p, vector<int> &V)
{
	if(!tree[node].empty()) memo.push_back(node);
	for(auto it : tree[node]) V.push_back(it);
	tree[node].clear();
	if(tl==tr) return;
	int mid=tl+tr>>1;
	if(p<=mid) get(node*2, tl, mid, p, V);
	else get(node*2+1, mid+1, tr, p, V);
}

void update(int node, int tl, int tr, int l, int r, int p)
{
	if(l<=tl && tr<=r)
	{
		tree[node].push_back(p);
		return;
	}
	if(r<tl || tr<l) return;
	int mid=tl+tr>>1;
	update(node*2, tl, mid, l, r, p);
	update(node*2+1, mid+1, tr, l, r, p);
}

struct UF
{
	int par[MAXN+10], opp[MAXN+10];

	void init()
	{
		for(int i=1; i<=N; i++)
		{
			par[i]=i;
			opp[i]=-1;
		}
	}

	int Find(int x)
	{
		if(x==par[x]) return par[x];
		return par[x]=Find(par[x]);
	}

	void Union(int x, int y)
	{
		x=Find(x); y=Find(y);
		if(opp[x]==y) return;
		if(x==y)
		{
			flag=false;
			return;
		}
		int xt=opp[x], yt=opp[y];

		if(yt!=-1) par[x]=yt;
		if(xt!=-1) par[y]=xt;
		x=par[x]; y=par[y];
		opp[x]=y; opp[y]=x;
	}
}uf;

int main()
{
	scanf("%d", &N);
	for(int i=1; i<=N; i++) scanf("%d%d", &A[i].first, &A[i].second);

	sort(A+1, A+N+1, [&](const pii &p, const pii &q)
	{
		return p.second<q.second;
	});
	
	uf.init();
	for(int i=1; i<=N; i++)
	{
		vector<int> V;
		get(1, 1, 2*N, A[i].first, V);
		for(auto it : V)
		{
			//printf("%d ", it);
			uf.Union(i, it);
			if(!flag) return !printf("0\n");
		}

		//printf(" : %d\n", i);
		//for(int j=1; j<=N; j++) printf("%d -> %d %d\n", j, uf.par[j], uf.opp[j]);
		int x=uf.Find(i), y=uf.opp[x];
		update(1, 1, 2*N, A[i].first, A[i].second, x);
		if(y!=-1) for(auto it : memo) tree[it].push_back(y);
		memo.clear();
	}

	int sz=0;
	for(int i=1; i<=N; i++)
	{
		if(uf.par[i]==i)
		{
			if(uf.opp[i]==-1) sz+=2;
			else sz++;
		}
	}
	sz/=2;

	ll ans=1;
	for(int i=1; i<=sz; i++)
	{
		ans*=2;
		ans%=MOD;
	}
	printf("%lld\n", ans);
}

Compilation message (stderr)

port_facility.cpp: In function 'void get(int, int, int, int, std::vector<int>&)':
port_facility.cpp:26:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |  int mid=tl+tr>>1;
      |          ~~^~~
port_facility.cpp: In function 'void update(int, int, int, int, int, int)':
port_facility.cpp:39:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |  int mid=tl+tr>>1;
      |          ~~^~~
port_facility.cpp: In function 'int main()':
port_facility.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   83 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
port_facility.cpp:84:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   84 |  for(int i=1; i<=N; i++) scanf("%d%d", &A[i].first, &A[i].second);
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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