Submission #533908

#	Time	Username	Problem	Language	Result	Execution time	Memory
533908		sare	Port Facility (JOI17_port_facility)	C++17	10 / 100	57 ms	86724 KiB

port_facility

//In the name of Allah :)
#include <bits/stdc++.h>
using namespace std;
string to_string(char c) { return string(1,c); }
string to_string(bool b) { return b ? "true" : "false"; }
string to_string(const char* s) { return (string)s; }
string to_string(string s) { return s; }
string to_string(vector<bool> v) { 
	string res = "{"; for(int i = 0; i < (int)v.size(); i++) res += char('0'+v[i]);
	res += "}"; return res; }
template<size_t SZ> string to_string(bitset<SZ> b) {
	string res = ""; for(size_t i = 0; i < SZ; i++) res += char('0'+b[i]);
	return res; }
template<class A, class B> string to_string(pair<A,B> p);
template<class T> string to_string(T v) { // containers with begin(), end()
	bool fst = 1; string res = "{";
	for (const auto& x: v) {
		if (!fst) res += ", ";
		fst = 0; res += to_string(x);
	}
	res += "}"; return res;
}
template<class A, class B> string to_string(pair<A,B> p) {
	return "("+to_string(p.first)+", "+to_string(p.second)+")"; }
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
	cerr << to_string(h); if (sizeof...(t)) cerr << ", ";
	DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL
#define wis(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "] : [", DBG(__VA_ARGS__)
#else
#define wis(...) 0
#endif
typedef long long ll;
#define all(x) (x).begin(), (x).end()
const int MAXN = 2e6 + 10, INF = 1e9, MOD = 1e9 + 7;
int n;
struct SegTree {
	bool t;
	int seg[MAXN << 2];

	SegTree (bool _t) {
		t = _t;
		if (t) {
			memset(seg, 63, sizeof(seg));
		}
	}
		
	int merge (int x, int y) {
		if (t) {
			return min(x, y);
		}
		return max(x, y);
	}

	void update (int nd, int cl, int cr, int ind, int x) {
		if (cr - cl == 1) {
			seg[nd] = x;
			return;
		}
		int L = nd << 1, R = L | 1, mid = (cl + cr) >> 1;
		if (ind < mid) {
			update(L, cl, mid, ind, x);
		}
		else {
			update(R, mid, cr, ind, x);
		}
		seg[nd] = merge(seg[L], seg[R]);
	}
	inline void update (int ind, int x) {
		update(1, 0, n + n, ind, x);
	}

	int get (int nd, int cl, int cr, int l, int r) {
		if (cl == l && cr == r) {
			return seg[nd];
		}
		int L = nd << 1, R = L | 1, mid = (cl + cr) >> 1, res = t ? INF : 0;
		if (l < mid) {
			res = merge(res, get(L, cl, mid, l, min(mid, r)));
		}
		if (r > mid) {
			res = merge(res, get(R, mid, cr, max(l, mid), r));
		}
		return res;
	}
	inline int get (int l, int r) {
		return get(1, 0, n + n, l, r);
	}

} seg1(1), seg2(0);
int l[MAXN], r[MAXN], type[MAXN], pw[MAXN], comp;
vector<int> adj[MAXN];
vector<pair<int, int>> ver;
bitset<MAXN> mark, color;

void dfs (int v, bool c) {
	assert(mark[v] == 0);
	int u;
	mark[v] = 1;
	ver.push_back({l[v], r[v]});
	color[v] = c;
	seg1.update(r[v], INF);
	seg2.update(l[v], 0);

	while ((u = seg1.get(l[v], r[v])) < l[v]) {
		dfs(type[u], c ^ 1);
	}
	while ((u = seg2.get(l[v], r[v])) > r[v]) {
		dfs(type[u], c ^ 1);
	}
}


int main() {
	ios::sync_with_stdio(0);
#ifndef LOCAL
	cin.tie(0);
#endif
	pw[0] = 1;
	for (int i = 1; i < MAXN; i++) {
		pw[i] = 2 * pw[i - 1] % MOD;
	}

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> l[i] >> r[i];
		type[l[i]] = type[r[i]] = i;
		seg1.update(r[i], l[i]);
		seg2.update(l[i], r[i]);
	}

	for (int i = 0; i < n; i++) {
		if (!mark[i]) {
			comp++;
			dfs(i, 0);

			vector<int> tmp, stk[2];
			for (auto x : ver) {
				tmp.push_back(x.first);
				tmp.push_back(x.second);
			}
			ver.clear();

			sort(all(tmp));
			for (int x : tmp) {
				int ind = type[x];
				if (l[ind] == x) {
					stk[color[ind]].push_back(ind);
				}
				else {
					if (stk[color[ind]].back() != ind) {
						cout << 0 << '\n';
						return 0;
					}
					else {
						stk[color[ind]].pop_back();
					}
				}
			}
		}
	}

	cout << pw[comp] << '\n';
}

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