Submission #70770

#	Time	Username	Problem	Language	Result	Execution time	Memory
70770		AlphaRazra	Port Facility (JOI17_port_facility)	C++14	100 / 100	2917 ms	383300 KiB

port_facility

#include<bits/stdc++.h>
#define mp make_pair
#define fs first
#define sc second
#define pb push_back
#define debug(x) cout<<#x<<" = "<<(x)<<endl
#define mod 1000000007
#define INF 1e18
using namespace std;

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
* if you have no idea just guess the appropriate well-known algo instead of doing nothing :/
*/

int n;
pair<int,int> tim[1000005];
int parent[2000005];

vector<int> tree[4 * 2000005];

int caribapak(int now){
	if(parent[now] == now) return now;
	return parent[now] = caribapak(parent[now]);
}

void gabung(int a,int b){
	int x = caribapak(a);
	int y = caribapak(b);
	if(x != y){
		parent[x] = y;
		return;
	}
}


void update(int idx,int l,int r,int pos,int val){
	if(pos > r || pos < l){
		return;
	}

	tree[idx].pb(val);
	if(l == r){
		return;
	}
	update(2 * idx, l, (l + r)/2, pos, val);
	update(2 * idx + 1, (l + r)/2 + 1, r, pos, val);
}

void query(int idx,int l,int r,int kiri,int kanan,int val){
	if(kiri > r || kanan < l){
		return;
	}

	if(l >= kiri && r <= kanan){
		for(int i = 0; i < tree[idx].size(); i++){
			int now = tree[idx][i];
		//	if(val == 4) cout << now << " tes\n";
			int com = now + n;
			if(now > n) com = now - n;
			gabung(now, val + n);
			gabung(com, val);
		}
		if(tree[idx].size() > 0){
			tree[idx].clear();
			tree[idx].pb(val + n);
		}
		return;
	}
	query(2 * idx, l, (l + r)/2, kiri, kanan, val);
	query(2 * idx + 1, (l + r)/2 + 1, r, kiri, kanan, val);
}

int main(){
	ios::sync_with_stdio(0);
	cin >> n;

	for(int i = 1 ; i <= n; i++){
		cin >> tim[i].fs >> tim[i].sc;
	}
	sort(tim + 1, tim + n + 1);

	for(int i = 1; i <= 2 * n; i++){
		parent[i] = i;
	}

	for(int i = 1; i <= n; i++){
		query(1, 1, 2 * n, tim[i].fs, tim[i].sc, i);
		int x=caribapak(i);
		int y=caribapak(n+i);
		if(x == y){
			cout << "0\n";
			return 0;
		}
		update(1, 1, 2 * n, tim[i].sc, i);
	}

	for(int i = 1; i <= n; i++){
		int x = caribapak(i);
		int y = caribapak(i + n);
		if(x == y){
		//	cout << i << " haha\n";
			cout << "0\n";
			return 0;
		}
	}

	long long ans = 1;
	int nyak = 0;
	for(int i = 1; i <= 2 * n; i++){
		if(caribapak(i) == i){
			nyak++;
		//	cout << i << " here\n";
		//	ans = (ans * 2) % mod;
		}
	}
	for(int i = 0; i < nyak / 2; i++){
		ans = (ans * 2) % mod;
	}

	cout << ans << "\n";


}

Compilation message (stderr)

port_facility.cpp: In function 'void query(int, int, int, int, int, int)':
port_facility.cpp:59:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < tree[idx].size(); i++){
                  ~~^~~~~~~~~~~~~~~~~~

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