Submission #550577

#	Time	Username	Problem	Language	Result	Execution time	Memory
550577		brunnorezendes	Port Facility (JOI17_port_facility)	C++14	0 / 100	0 ms	340 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], sz[maxn], vis[maxn];

sii ini, fim, aux;
sii::iterator initial, last;
vii truck, ordered;

ll exp(ll a, int b){
	ll x;
	if(b==1) return a;
	if(b&1) return (a*exp(a, b-1))%(ll)mod;
	else{
		x = exp(a, b/2);
		return (x*x)%(ll)mod;
	}
}

int find(int x){
	if(dsu[x]==x) return x;
	else{
		dsu[x] = find(dsu[x]);
		return dsu[x];
	}
}

void merge(int a, int b){
	int winb, wina;
	a = find(a);
	b = find(b);
	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];
			sz[dsu[a]] += sz[a];
		}
		else if(opo[b]==-1){
			dsu[b] = opo[a];
			sz[dsu[b]] += sz[b];
		}
		else{
			if(sz[opo[a]]>sz[b]){
				dsu[b] = opo[a];
				sz[opo[a]] += sz[b];
				winb = opo[a];
			}
			else{
				dsu[opo[a]] = b;
				sz[b] += sz[opo[a]];
				winb = b;
			}
			if(sz[opo[b]]>sz[a]){
				dsu[a] = opo[b];
				sz[opo[b]] += sz[a];
				wina = opo[b];
			}
			else{
				dsu[opo[b]] = a;
				sz[a] += sz[opo[b]];
				wina = a;
			}
			opo[wina] = winb;
			opo[winb] = wina;
		}
	}
}

int main(){
	int n, i, a, b, u, tam=0;
	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;
		sz[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) aux.insert({(*initial).s, 0});
			initial++;
		}
		initial = fim.upper_bound({truck[u].f, u});
		last = fim.upper_bound({truck[u].s, u});
		while(initial!=last){
			if((*initial).s!=u){
				if(aux.count({(*initial).s, 0})) aux.erase({(*initial).s, 0});
				else aux.insert({(*initial).s, 0});
			}
			initial++;
		}
		initial = aux.begin();
		last = aux.end();
		while(initial!=last){
			merge(u, (*initial).f);
			if(flag) break;
			initial++;
		}
		if(flag) break;
		ini.erase({truck[u].f, u});
		fim.erase({truck[u].s, u});
		aux.clear();
	}
	if(flag) cout << "0";
	else{
		for(i=0;i<n;i++){
			a = find(i);
			if(opo[a]==-1 || !vis[opo[a]]) tam++;
			vis[a]=1;
		}
		cout << exp(2, tam);
	}
	return (0);
}

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