Submission #23683

#	Time	Username	Problem	Language	Result	Execution time	Memory
23683		rubabredwan	Port Facility (JOI17_port_facility)	C++14	0 / 100	36 ms	259864 KiB

port_facility

/*  Bismillahir Rahmanir Rahim  */

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int N = 2000005;
const int oo = 1e9;

struct segtree{
	int n; 
	pii t[N*4];
	void init(int _n){
		n = _n;
		for(int i=0;i<N*4;i++) t[i] = {oo, oo};
	}
	void update(int b, int e, int node, int pos, int val){
		if(b == e){
			t[node] = {val, b};
			return;
		}
		int mid = (b + e) / 2, l = 2 * node, h = l + 1;
		if(pos <= mid) update(b, mid, l, pos, val);
		else update(mid+1, e, h, pos, val);
		t[node] = min(t[l], t[h]);
	}
	void update(int pos, int val){
		update(1, n, 1, pos, val);
	}
	pii query(int b, int e, int node, int x, int y){
		if(y < b || e < x) return {oo, oo};
		if(b >= x && e <= y) return t[node];
		int mid = (b + e) / 2, l = 2 * node, h = l + 1;
		return min(query(b, mid, l, x, y), query(mid+1, e, h, x, y));
	}
	pii query(int x, int y){
		return query(1, n, 1, x, y);
	}
};

struct dsu{
	int n, par[N], en[N], siz[N], vis[N];
	void init(int _n){
		n = _n;
		for(int i=0;i<=n;i++) par[i] = i, siz[i] = 1, en[i] = 0;
	}
	int Find(int at){
		return par[at] == at ? at : par[at] = Find(par[at]);
	}
	void Union(int a, int b){
		a = Find(a), b = Find(b);
		if(a == b) return;
		if(siz[a] > siz[b]) par[b] = a, siz[a] += siz[b];
		else par[a] = b, siz[b] += siz[a];
	}
	bool isFriend(int a, int b){
		if(Find(a) == Find(b)) return true;
		else return false;
	}
	bool isEnemy(int a, int b){
		a = Find(a), b = Find(b);
		if(Find(en[a]) == Find(b)) return true;
		if(Find(en[b]) == Find(a)) return true;
		return false;
	}
	void makeFriend(int a, int b){
		a = Find(a), b = Find(b);
		if(a == b) return;
		if(en[a] && en[b]) Union(en[a], en[b]);
		if(!en[a]) en[a] = Find(en[b]);
		if(!en[b]) en[b] = Find(en[a]);
		Union(a, b);
	}
	void makeEnemy(int a, int b){
		a = Find(a), b = Find(b);
		if(a == b) return;
		if(!en[a]) en[a] = b;
		else Union(en[a], b);
		if(!en[b]) en[b] = a;
		else Union(en[b], a);
	}
    int get(){
        int ret = 0;
        memset(vis, 0, sizeof(vis));
        for(int i=1;i<=n;i++){
            if(vis[Find(i)]) continue;
            vis[Find(i)] = 1;
            vis[Find(en[Find(i)])] = 1;
            ++ret;
        }
        return ret;
    }
};

int n, st[N], en[N], idx[N];
set<int>ms[N];
vector<int>vec[N];
segtree tree;
dsu ds;

int get_prev(int a, int b){
	auto it = ms[a].lower_bound(b);
	if(it == ms[a].begin()) return 0;
	else *(--it);
}

void solve(){
	for(int i=2*n;i>=1;i--){
		int id = idx[i];
		int l = st[id], r = en[id];
		if(i == st[id]) continue;
		int cur = l;
		pii mx = {-1, -1};
		while(cur < r){
			pii f = tree.query(cur, r);
			if(f.first > cur) break;
			int pos = f.second, fk = ds.Find(idx[pos]);
			if(ds.isFriend(id, fk)){
				printf("0\n");
				return;
			}
			mx = max(mx, {ds.siz[fk], fk});
			cur = pos + 1;
		}
		if(mx.first == -1){
			tree.update(l, 0);
			ms[id].insert(l);
		}
		else{
			cur = l;
			int p = get_prev(mx.second, l);
			ds.makeEnemy(id, mx.second);

			while(cur < r){
				pii f = tree.query(cur, r);
				if(f.first > cur) break;
				int pos = f.second, fk = idx[pos];
				if(ds.isEnemy(mx.second, fk)){
					printf("0\n");
					return;
				}
				ds.makeFriend(mx.second, fk);
                ms[mx.second].insert(pos);
				tree.update(pos, p);
				p = pos;
				cur = pos + 1;
			}

            tree.update(l, get_prev(ds.Find(id), l));

		}
	}
	int comp = ds.get();
	long long ret = 1LL;
	long long mod = 1e9 + 7;
	for(int i=1;i<=comp;i++){
		ret *= 2LL;
		ret %= mod;
	}
	printf("%lld\n", ret);
}

int main(){
	scanf("%d", &n);
	for(int i=1;i<=n;i++){
		scanf("%d %d", &st[i], &en[i]);
		idx[st[i]] = i;
		idx[en[i]] = i;
	}
	tree.init(2*n);
	ds.init(n);
	solve();
	return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int get_prev(int, int)':
port_facility.cpp:107:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
port_facility.cpp: In function 'int main()':
port_facility.cpp:166:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
port_facility.cpp:168:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &st[i], &en[i]);
                                 ^

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