Submission #550591

#	Time	Username	Problem	Language	Result	Execution time	Memory
550591		brunnorezendes	Port Facility (JOI17_port_facility)	C++17	22 / 100	6047 ms	13844 KiB

port_facility

#include <bits/stdc++.h>
#define f first
#define s second
#define maxn 1000001
#define mod 1000000007
 
using namespace std;
 
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef set<ii> sii;
typedef long long int ll;
 
int dsu[maxn], flag=0, opo[maxn], vis[maxn];
 
sii ini, fim;
sii::iterator initial, last;
vii truck, ordered;
 
int find(int x){
	if(x == -1) return -1;
	if(dsu[x]==x) return x;
	else{
		dsu[x] = find(dsu[x]);
		return dsu[x];
	}
}
 
void merge(int a, int b){
	a = find(a);
	b = find(b);
	opo[b] = find(opo[b]);
	opo[a] = find(opo[a]);
	if(a == b) flag=1;
	else{
		if(opo[a]==-1 && opo[b]==-1){
			opo[a] = b;
			opo[b] = a;
		}
		else if(opo[a]==-1){
			dsu[a] = opo[b];
		}
		else if(opo[b]==-1){
			dsu[b] = opo[a];
		}
		else{
			dsu[b] = opo[a];
			dsu[opo[b]] = a;
		}
	}
}
 
int main(){
	int n, i, a, b, u, tam=1;
	cin >> n;
	for(i=0;i<n;i++){
		cin >> a >> b;
		a--;b--;
		truck.push_back({a, b});
		ordered.push_back({b-a, i});
		ini.insert({a, i});
		fim.insert({b, i});
		dsu[i]=i;
		opo[i]=-1;
	}
	sort(ordered.begin(), ordered.end());
	for(i=0;i<n;i++){
		u = ordered[i].s;
		initial = ini.upper_bound({truck[u].f, u});
		last = ini.upper_bound({truck[u].s, u});
		while(initial!=last){
			if((*initial).s!=u) merge(u, (*initial).s);
			if(flag) break;
			initial++;
		}
		initial = fim.upper_bound({truck[u].f, u});
		last = fim.upper_bound({truck[u].s, u});
		while(initial!=last){
			if((*initial).s!=u) merge(u, (*initial).s);
			if(flag) break;
			initial++;
		}
		if(flag) break;
		ini.erase({truck[u].f, u});
		fim.erase({truck[u].s, u});
	}
	if(flag) cout << "0";
	else{
		for(i=0;i<n;i++){
			a = find(i);
			if(!vis[a] && (opo[a]==-1 || !vis[opo[a]])) tam+=tam;
			if(tam>=mod) tam-=mod;
			vis[a]=1;
		}
		cout << tam;
	}
	return (0);
}

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