Submission #134963

#	Time	Username	Problem	Language	Result	Execution time	Memory
134963		mirbek01	Port Facility (JOI17_port_facility)	C++11	0 / 100	2 ms	376 KiB

port_facility

# include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 2;
const int mod = 1e9 + 7;

struct st{
	int a, b;
}
ar[N];

int n, fen[N + N], p[N], sz[N];
int t[N * 8];

void upd_sum(int pos){
	for(int i = pos; i < N + N; i |= i + 1)
		fen[i] ++;
}

int get(int r){
	int ret = 0;
	for(int i = r; i > 0; i = (i & (i + 1)) - 1)
		ret += fen[i];
	return ret;
}

int get_sum(int l, int r){
	return get(r) - get(l - 1);
}

int f_s(int v){
	return (p[v] == v)?v:p[v] = f_s(p[v]);
}

void u_s(int a, int b){
	a = f_s(a);
	b = f_s(b);
	if(a != b){
		if(sz[a] < sz[b])
			swap(a, b);
		p[b] = a;
		sz[a] += sz[b];
	}
}

void upd_max(int pos, int val, int v = 1, int tl = 1, int tr = 2 * n){
	if(tl == tr)
		t[v] = val;
	else {
		int tm = (tl + tr) >> 1;
		if(pos <= tm)
			upd_max(pos, val, v << 1, tl, tm);
		else 
			upd_max(pos, val, v << 1 | 1, tm + 1, tr);
		t[v] = max(t[v << 1], t[v << 1 | 1]);
	}
}

int get_max(int l, int r, int v = 1, int tl = 1, int tr = 2 * n){
	if(l > tr || tl > r)
		return 0;
	if(l <= tl && tr <= r)
		return t[v];
	int tm = (tl + tr) >> 1;
	return max(get_max(l, r, v << 1, tl, tm), get_max(l, r, v << 1 | 1, tm + 1, tr));
}

int main(){
	cin >> n;
	
	for(int i = 1; i <= n; i ++){
		scanf("%d %d", &ar[i].a, &ar[i].b);
		p[i] = i, sz[i] = 1;
	}
	sort(ar + 1, ar + n + 1, [&](st a, st b){
						return a.a < b.a;});
	
	for(int i = 1; i <= n; i ++){
		int cnt = get_sum(ar[i].a, ar[i].b);
		if(cnt > 1){
			cout << 0 << endl;
			return 0;
		}
		upd_sum(ar[i].b);
		int mx = get_max(ar[i].a, ar[i].b);
		if(mx > 0){
			u_s(i, mx);
		}
		upd_max(ar[i].b, i);
	}
	
	int ans = 1;
	
	for(int i = 1; i <= n; i ++){
		if(p[i] == i)
			ans = (ans * 2) % mod;
	}
	
	cout << ans << endl;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &ar[i].a, &ar[i].b);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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