#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
const ll MAXN = 1E6+16, MOD = 1E9+7, IDEM = ll(1E18)+16;
vll adj[MAXN];
bool col[MAXN];
bool vis[MAXN];
#define mid ((l+r)>>1)
#define off (2*(mid-l+1))
struct SegTree {
struct Node {
ll minN, maxN;
Node (ll valmin, ll valmax): minN(valmin), maxN(valmax) {}
Node (): minN(IDEM), maxN(-IDEM) {} // INF
Node operator+ (const Node &o) {
Node ans;
ans.minN = min(minN, o.minN);
ans.maxN = max(maxN, o.maxN);
return ans;
}
};
vector <Node> tree;
ll n;
SegTree (ll n): tree(2*n, Node()), n(n) {}
void update (ll at, Node node) { update(at, node, 0, n-1, 0); }
void update (ll at, Node node, ll l, ll r, ll id) {
if (at < l || r < at) return;
if (at <= l && r <= at) { tree[id] = node; return; }
update(at, node, l, mid, id+1);
update(at, node, mid+1, r, id+off);
tree[id] = tree[id+1] + tree[id+off];
}
void idemize (ll at) { update(at, Node()); } // idempotentize
Node query (ll ql, ll qr) { return query(ql, qr, 0, n-1, 0); }
Node query (ll ql, ll qr, ll l, ll r, ll id) {
if (qr < l || r < ql) return Node(); // IDEM node
if (ql <= l && r <= qr) return tree[id];
return query(ql, qr, l, mid, id+1) + query(ql, qr, mid+1, r, id+off);
}
};
bool dfs_paint (ll u, ll par) {
if (vis[u]) return false;
vis[u] = true;
for (ll v : adj[u]) {
if (v == par) continue;
col[v] = !col[u];
dfs_paint(v, u);
}
return true;
}
int main () {
cin.tie(nullptr) -> sync_with_stdio(false);
ll n;
cin >> n;
vll who(2*n);
vector <pair <ll, ll> > ve(n);
for (auto &[l, r] : ve) { cin >> l >> r; l--; r--; }
for (ll i = 0; i < n; i++) { auto [l, r] = ve[i]; who[l] = i; who[r] = i; }
SegTree st(2*n);
for (ll i = 0; i < n; i++) {
auto [l, r] = ve[i];
st.update(l, SegTree::Node(IDEM, r));
st.update(r, SegTree::Node(l, -IDEM));
}
// we draw edges between intersecting segments, and then delete them
for (ll i = 0; i < n; i++) {
auto [l, r] = ve[i];
{SegTree::Node th;
while (th = st.query(l, r), th.maxN > r) {
adj[i].push_back(who[th.maxN]);
adj[who[th.maxN]].push_back(i);
auto [aul, aur] = ve[who[th.maxN]];
st.idemize(aul);
st.idemize(aur);
}}
{SegTree::Node th;
while (th = st.query(l, r), th.minN < l) {
adj[i].push_back(who[th.minN]);
adj[who[th.minN]].push_back(i);
auto [aul, aur] = ve[who[th.minN]];
st.idemize(aul);
st.idemize(aur);
}}
}
// we get a forest of trees, not all edges are drawn in this process, but all interlocked nodes are connected
ll ans = 1;
// we paint them accordingly (a tree is always bipartite)
for (ll u = 0; u < n; u++) if (dfs_paint(u, u)) ans = 2*ans % MOD;
// we check the extra edges that we didn't draw by straight up simulating it
stack <ll> stA, stB;
for (ll i = 0; i < 2*n; i++) {
ll u = who[i];
if (col[u] == 0) if (stA.size() && stA.top() == u) stA.pop(); else stA.push(u);
if (col[u] == 1) if (stB.size() && stB.top() == u) stB.pop(); else stB.push(u);
}
if (stA.size() == 0 && stB.size() == 0) cout << ans << '\n';
else cout << "0\n";
// we check whether the process concluded successfully or not
return 0;
}
Compilation message
port_facility.cpp: In function 'int main()':
port_facility.cpp:104:12: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
104 | if (col[u] == 0) if (stA.size() && stA.top() == u) stA.pop(); else stA.push(u);
| ^
port_facility.cpp:105:12: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
105 | if (col[u] == 1) if (stB.size() && stB.top() == u) stB.pop(); else stB.push(u);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
25692 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
25692 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
25692 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
25692 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
