Submission #286680

#	Time	Username	Problem	Language	Result	Execution time	Memory
286680		YJU	Port Facility (JOI17_port_facility)	C++14	0 / 100	32 ms	47352 KiB

port_facility

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=2e6+5;
const ld pi=3.14159265359;
const ll INF=(1LL<<60);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()

ll n,x[N],y[N],l[N],r[N],nxt[N],ans=1,col[N],k[N];
vector<ll> v[N];

void DFS(ll id){
	for(auto i:v[id]){
		if(col[i]){if(col[i]+col[id]!=3)ans*=0;continue;}
		col[i]=3-col[id];
		DFS(i);
	}
}

void me(ll ida,ll idb){
	v[ida].pb(idb);v[idb].pb(ida);
}
 
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n;
	REP1(i,n)cin>>x[i]>>y[i],l[x[i]]=r[y[i]]=i;
	REP1(i,2*n)nxt[i]=i-1;
	REP1(i,2*n){
		if(l[i]){
			ll L=x[l[i]],R=y[l[i]],to=nxt[R];
			for(ll j=nxt[R];j>L;j=nxt[j]){
				if(k[j]){
					me(l[i],k[j]);
				}
				to=j;
			}
			for(ll j=nxt[R];j>L&&j!=to;j=nxt[j]){
				nxt[j]=to;
			}
			k[y[l[i]]]=l[i];
		}else{
			k[y[r[i]]]=0;
		}
	}
	REP1(i,n){
		if(col[i]==0){
			ans=ans*2%MOD;
			col[i]=1;
			DFS(i);
		}
	}
	cout<<ans<<"\n";	
	return 0;
}
 

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