Submission #21694

#	Time	Username	Problem	Language	Result	Execution time	Memory
21694		pacu	Port Facility (JOI17_port_facility)	C++98	78 / 100	3500 ms	126912 KiB

port_facility

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

int N;
int t1[1000000], t2[1000000];

int fid[2000001];
int sz[2000001];

void init()
{
	for(int i=0;i<2*N;i++)
		fid[i] = i, sz[i] = 1;
}

int find(int i)
{
	if(fid[i]==i) return i;
	return fid[i] = find(fid[i]);
}

void join(int i,int j)
{
	i = find(i), j = find(j);
	if(i==j) return;
	if(sz[i] <= sz[j])
	{
		fid[i] = j;
		sz[j] += sz[i];
	}
	else
	{
		fid[j] = i;
		sz[i] += sz[j];
	}
}

void sameEdge(int i,int j)
{
	//cout << "same " << i << ' ' << j << '\n';
	join(2*i,2*j);
	join(2*i+1,2*j+1);
}
void difEdge(int i,int j)
{
	join(2*i+1,2*j);
	join(2*i,2*j+1);
}

#define SEG (1<<21)
int up[2*SEG],l[2*SEG],r[2*SEG],seg[2*SEG],cont[2*SEG];
int rIndex[2000000];

void segInit()
{
	for(int i=SEG;i<2*SEG;i++)
		l[i] = r[i] = i-SEG, up[i] = -1;
	for(int i=SEG-1;i>0;i--)
		l[i] = l[2*i], r[i] = r[2*i+1], up[i] = -1;
}

void push(int i)
{
	if(up[i]>-1)
	{
		if(i<SEG)
		{
			if(up[2*i]>-1 && seg[2*i]>0) sameEdge(up[i],up[2*i]);
			if(up[2*i+1]>-1 && seg[2*i+1]>0) sameEdge(up[i],up[2*i+1]);
			up[2*i] = up[2*i+1] = up[i];
		}
		else if(rIndex[i-SEG]>-1 && cont[i])
		{
			difEdge(rIndex[i-SEG],up[i]);
		}
		up[i] = -1;
	}
}

int low,high;
void update(int i,int p)
{
	if((l[i]>high)||(r[i]<low)||(seg[i]==0)) return;
	if((l[i]>=low)&&(r[i]<=high))
	{
		push(i);
		//cout << "Set " << p << " at " << l[i] << " to " << r[i] << '\n';
		up[i] = p;
		return;
	}
	push(i);
	update(2*i,p);
	update(2*i+1,p);
}

int getSum(int i)
{
	if((l[i]>high)||(r[i]<low)) return 0;
	if((l[i]>=low)&&(r[i]<=high)) return seg[i];
	return getSum(2*i) + getSum(2*i+1);
}

void add(int i)
{
	int j = 1;
	while(j < SEG)
	{
		push(j);
		seg[j]++;
		if(i <= r[2*j]) j = 2*j;
		else j = 2*j+1;
	}
	push(j);
	cont[i+SEG] = 1;
	seg[i+SEG] = 1;
}

int compAns[2000000];
int cid[1000000];

bool cmp(int a,int b)
{
	return t1[a]<t1[b];
}

int main()
{
	scanf("%d",&N);
	for(int i=0;i<N;i++)
	{
		scanf("%d %d",&t1[i],&t2[i]);
		rIndex[t1[i]] = -1;
		rIndex[t2[i]] = i;
		cid[i] = i;
	}
	sort(cid,cid+N,cmp);
	init();
	segInit();
	for(int i=0;i<N;i++)
	{
		low = t1[cid[i]];
		high = t2[cid[i]];
		update(1,cid[i]);
		add(t2[cid[i]]);
	}
	for(int i=1;i<2*SEG;i++)
		push(i);
	for(int i=0;i<N;i++)
	{
		if(find(2*i) == find(2*i+1))
		{
			printf("0\n");
			return 0;
		}
	}
	int cmp = 0;
	for(int i=0;i<2*N;i++)
		if(find(i)==i)
			cmp++;
	int ans = 1;
	for(int i=0;i<cmp/2;i++)
		ans = (2*ans)%1000000007;
	printf("%d\n",ans);
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:132:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&N);
                ^
port_facility.cpp:135:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&t1[i],&t2[i]);
                               ^

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