Submission #635293

#	Time	Username	Problem	Language	Result	Execution time	Memory
635293		GusterGoose27	Port Facility (JOI17_port_facility)	C++11	100 / 100	1914 ms	615112 KiB

port_facility

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e6;
const int inf = 1e9;
const int MOD = 1e9+7;
int n;
int atl[2*MAXN];
int atr[2*MAXN];
vector<int> deact;

class mintree {
public:
	int mn = inf;
	mintree *l = nullptr;
	mintree *r = nullptr;
	int lp, rp;
	mintree(int lv, int rv, int arr[]) {
		lp = lv;
		rp = rv;
		if (lp == rp) {
			if (arr[lp] != -1) mn = arr[lp];
		}
		else {
			int m = (lp+rp)/2;
			l = new mintree(lp, m, arr);
			r = new mintree(m+1, rp, arr);
			mn = min(l->mn, r->mn);
		}
	}
	int query(int lv, int rv) {
		if (lp > rv || rp < lv) return inf;
		if (lp >= lv && rp <= rv) return mn;
		return min(l->query(lv, rv), r->query(lv, rv));
	}
	void upd(int p, int v) {
		if (lp > p || rp < p) return;
		if (lp == rp) {
			if (v == -1) mn = inf;
			else mn = v;
			return;
		}
		l->upd(p, v);
		r->upd(p, v);
		mn = min(l->mn, r->mn);
	}
	int l_contain(int l_lim, int l_req) {
		if (rp < l_lim || mn >= l_req) return inf;
		if (lp == rp) return lp;
		int ans = l->l_contain(l_lim, l_req);
		if (ans < inf) return ans;
		return r->l_contain(l_lim, l_req);
	}
};

class maxtree {
public:
	int mx = -1;
	maxtree *l = nullptr;
	maxtree *r = nullptr;
	int lp, rp;
	maxtree(int lv, int rv, int arr[]) {
		lp = lv;
		rp = rv;
		if (lp == rp) {
			mx = arr[lp];
		}
		else {
			int m = (lp+rp)/2;
			l = new maxtree(lp, m, arr);
			r = new maxtree(m+1, rp, arr);
			mx = max(l->mx, r->mx);
		}
	}
	int query(int lv, int rv) {
		if (lp > rv || rp < lv) return -1;
		if (lp >= lv && rp <= rv) return mx;
		return max(l->query(lv, rv), r->query(lv, rv));
	}
	void upd(int p, int v) {
		if (lp > p || rp < p) return;
		if (lp == rp) {
			mx = v;
			return;
		}
		l->upd(p, v);
		r->upd(p, v);
		mx = max(l->mx, r->mx);
	}
};

mintree *close_contain; // min left
maxtree *far_inter; // max right
mintree *close_inter; // min left
int uf[MAXN];
int sz[MAXN];
bool flip[MAXN];
int id[2*MAXN];

int find(int i) {
	if (uf[i] == -1) return i;
	int np = find(uf[i]);
	flip[i] ^= flip[uf[i]];
	return uf[i] = np;
}

void merge(int a, int b, bool f) {
	int ia = find(a);
	int ib = find(b);
	if (ia == ib) {
		if ((flip[a]^flip[b]) != f) {
			cout << '0' << endl;
			exit(0);
		}
		return;
	}
	uf[ib] = ia;
	sz[ia] += sz[ib];
	flip[ib] = flip[a]^flip[b]^f;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	fill(atl, atl+2*n, -1);
	fill(atr, atr+2*n, -1);
	fill(uf, uf+n, -1);
	fill(sz, sz+n, 1);
	for (int i = 0; i < n; i++) {
		int l, r; cin >> l >> r; l--; r--;
		atr[l] = r;
		atl[r] = l;
		id[l] = id[r] = i;
	}
	close_contain = new mintree(0, 2*n-1, atl);
	far_inter = new maxtree(0, 2*n-1, atr);
	close_inter = new mintree(0, 2*n-1, atl);
	for (int i = 0; i < 2*n; i++) {
		if (atr[i] == -1) continue;
		int r_cont = close_contain->l_contain(atr[i]+1, i);
		assert(r_cont > atr[i]);
		if (r_cont < inf) {
			int mx_r = far_inter->query(i, atr[i]);
			if (mx_r > r_cont) merge(id[i], id[r_cont], 0);
		}
		int lp = close_inter->query(atr[i]+1, r_cont-1);
		while (lp <= atr[i]) {
			deact.push_back(lp);
			merge(id[i], id[lp], 1);
			close_inter->upd(atr[lp], -1);
			lp = close_inter->query(atr[i]+1, r_cont-1);
		}
		for (int v: deact) close_inter->upd(atr[v], v);
		deact.clear();
	}
	int ans = 1;
	for (int i = 0; i < n; i++) {
		if (uf[i] == -1) {
			ans *= 2;
			ans %= MOD;
		}
	}
	cout << ans << "\n";
}

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