Submission #411090

#	Time	Username	Problem	Language	Result	Execution time	Memory
411090		alishahali1382	Port Facility (JOI17_port_facility)	C++14	100 / 100	1309 ms	69452 KiB

port_facility

#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int MAXN=1000010, LOG=20;

int n, m, k, u, v, x, y, t, a, b, ans;
int A[MAXN], B[MAXN];
int L[MAXN], R[MAXN];
int par[MAXN], parx[MAXN];
int seg[MAXN<<3];
bool sz[MAXN<<3];

pii getpar(int x){
	if (par[x]==x) return {x, 0};
	pii p=getpar(par[x]);
	par[x]=p.first;
	parx[x]^=p.second;
	return {par[x], parx[x]};
}
int join(int x, int y, int w){
	pii xx=getpar(x);
	pii yy=getpar(y);
	if (xx.first!=yy.first){
		par[xx.first]=yy.first;
		parx[xx.first]=xx.second^yy.second^w;
		ans--;
		return 1;
	}
	if (xx.second^yy.second^w){
		cout<<"0\n";
		exit(0);
	}
	return 0;
}
void Set(int id, int tl, int tr, int pos, int x){
	if (pos<tl || tr<=pos) return ;
	sz[id]=1;
	if (tr-tl==1){
		seg[id]=x;
		return ;
	}
	int mid=(tl+tr)>>1;
	Set(id<<1, tl, mid, pos, x);
	Set(id<<1 | 1, mid, tr, pos, x);
	seg[id]=0;
	if (!sz[id<<1] || !sz[id<<1 | 1]) seg[id]=seg[id<<1]+seg[id<<1 | 1];
}
void Merge(int id, int tl, int tr, int l, int r, int x){
	if (r<=tl || tr<=l || !sz[id]) return ;
	if (l<=tl && tr<=r){
		if (seg[id]) join(x, seg[id], 1);
		else{
			int mid=(tl+tr)>>1;
			Merge(id<<1, tl, mid, l, r, x);
			Merge(id<<1 | 1, mid, tr, l, r, x);
			seg[id]=max(seg[id<<1], seg[id<<1 | 1]);
		}
		return ;
	}
	int mid=(tl+tr)>>1;
	Merge(id<<1, tl, mid, l, r, x);
	Merge(id<<1 | 1, mid, tr, l, r, x);
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n;
	for (int i=1; i<=n; i++){
		cin>>L[i]>>R[i];
		B[L[i]]=i;
		B[R[i]]=-i;
		par[i]=i;
	}
	ans=n;
	for (int i=1; i<=2*n; i++) if (B[i]>0){
		int x=B[i];
		Set(1, 1, 2*n+1, R[x], x);
		Merge(1, 1, 2*n+1, L[x], R[x], x);
	}	
	
	ll res=1;
	while (ans--) res=res*2%mod;
	cout<<res<<"\n";
	
	return 0;
}

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