Submission #999562

#	Time	Username	Problem	Language	Result	Execution time	Memory
999562		Tob	Port Facility (JOI17_port_facility)	C++14	100 / 100	1518 ms	243472 KiB

port_facility

#include <bits/stdc++.h>

#pragma gcc("O3, unroll-loops")

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

const int N = 1e6 + 7, ofs = (1 << 21), mod = 1e9 + 7;

int n, E;
int l[N], r[N], par[N], siz[N], bio[N], col[N];
pii t[2*ofs];
vector <int> no[N], adj[N];

void add(int x, int y) {
	x += ofs;
	t[x] = {y, y};
	while (x /= 2) t[x] = {max(t[2*x].F, t[2*x+1].F), min(t[2*x].S, t[2*x+1].S)};
}
pii get(int x, int a, int b, int lo = 0, int hi = ofs-1) {
	if (b < lo || hi < a) return {-1, n};
	if (a <= lo && hi <= b) return t[x];
	int mid = (lo + hi) / 2;
	pii p1 = get(2*x, a, b, lo, mid), p2 = get(2*x+1, a, b, mid+1, hi);
	return {max(p1.F, p2.F), min(p1.S, p2.S)};
}

int find(int x) {return (x == par[x]) ? x : (par[x] = find(par[x]));}
void unite(int x, int y) {
	x = find(x); y = find(y);
	if (x == y) return;
	if (siz[x] < siz[y]) swap(x, y);
	siz[x] += siz[y];
	par[y] = x;
	for (auto z : no[y]) {
		add(r[z], x);
		no[x].pb(z);
	}
}

void dfs(int x) {
	bio[x] = 1;
	for (auto y : adj[x]) {
		if (bio[y]) {
			if (col[x] == col[y]) E = 1;
			continue;
		}
		col[y] = col[x] ^ 1;
		dfs(y);
	}
}

int madd(int x, int y) {return (x+y < mod) ? (x+y) : (x+y-mod);}
int mul(int x, int y) {return (ll)x*y%mod;}

int main () {
	FIO;
	cin >> n;
	for (int i = 0; i < 2*ofs; i++) t[i] = {-1, n};
	
	vector <pii> v;
	
	for (int i = 0; i < n; i++) {
		cin >> l[i] >> r[i]; l[i]--; r[i]--;
		par[i] = i;
		siz[i] = 1;
		v.pb({l[i], i});
		no[i] = {i};
	}
	sort(all(v));
	
	vector <pii> ed;
	
	for (int i = 0; i < n; i++) {
		int x = v[i].S;
		pii o = get(1, l[x], r[x]);
		if (o.F != -1 && o.F != o.S) {
			while (o.F != o.S) {
				unite(o.F, o.S);
				o = get(1, l[x], r[x]);
			}
		}
		if (o.F != -1) {
			ed.pb({o.F, x});
		}
		add(r[x], x);
	}
	
	for (int i = 0; i < ed.size(); i++) {
		int x = find(ed[i].F), y = find(ed[i].S);
		adj[x].pb(y);
		adj[y].pb(x);
	}
	
	int res = 1;
	for (int i = 0; i < n; i++) {
		int x = find(i);
		if (bio[x]) continue;
		res = mul(res, 2);
		dfs(x);
	}
	
	cout << ((E) ? 0 : res);

	return 0;
}

Compilation message (stderr)

port_facility.cpp:3: warning: ignoring '#pragma gcc ' [-Wunknown-pragmas]
    3 | #pragma gcc("O3, unroll-loops")
      | 
port_facility.cpp: In function 'int main()':
port_facility.cpp:97:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |  for (int i = 0; i < ed.size(); i++) {
      |                  ~~^~~~~~~~~~~

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