#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int mod = 998'244'353;
struct DisjointSet{
public:
int n;
vector<int> par;
void Init(int _n) {
n = _n;
par.resize(n);
iota(par.begin(), par.end(), 0);
}
int Find(int x) {
if (par[x] == x) return x;
return par[x] = Find(par[x]);
}
void Union(int x, int y) {
x = Find(x);
y = Find(y);
if (x == y) return;
par[y] = x;
}
} dsu;
struct SegmentTree{
public:
int n;
vector<int> tree;
void Init(int _n) {
n = _n;
int sz = 1<<(Log2(n)+1);
tree.resize(sz);
fill(tree.begin(), tree.end(), -1);
}
void Update(int tar, int val) { Update(1, 1, n, tar, val); }
int Query(int l, int r) { return Query(1, 1, n, l, r); }
private:
static int Log2(int n) {
int ret = 0;
while (n > 1 << ret) ret ++;
return ret;
}
void Update(int node, int s, int e, int tar, int val) {
if (s > tar || tar > e) return;
if (s == e) {
tree[node] = val;
return;
}
int mid = s + e >> 1;
Update(node<<1, s, mid, tar, val);
Update(node<<1|1, mid+1, e, tar, val);
tree[node] = max(tree[node<<1], tree[node<<1|1]);
}
int Query(int node, int s, int e, int l, int r) {
if (l > e || s > r) return -1;
if (l <= s && e <= r) return tree[node];
int mid = s + e >> 1;
return max(Query(node<<1, s, mid, l, r), Query(node<<1|1, mid+1, e, l, r));
}
} seg;
int main() {
ios_base :: sync_with_stdio(false); cin.tie(NULL);
int n;
cin >> n;
vector<pii> a(n);
vector<int> chk(2*n, 0);
for (int i=0; i<n; i++) {
cin >> a[i].first >> a[i].second;
}
sort(a.begin(), a.end());
seg.Init(2*n);
dsu.Init(2*n);
for (int i=0; i<n; i++) {
vector<int> v;
while (true) {
int ret = seg.Query(a[i].first, a[i].second);
if (ret == -1) break;
v.push_back(ret);
seg.Update(a[ret].second, -1);
}
if (!v.empty()) {
sort(v.begin(), v.end(), [&] (int &u, int &v) { return a[u].first < a[v].first; });
for (int j=0; j<(int)v.size()-1; j++) {
if (a[v[j]].second < a[v[j+1]].second) {
cout << "0\n";
return 0;
}
}
for (auto &x : v) {
chk[dsu.Find(x<<1)] = 1;
if (chk[dsu.Find(x<<1)^1]) {
cout << "0\n";
return 0;
}
}
for (auto &x : v) chk[dsu.Find(x<<1)] = 0;
int g = dsu.Find(v[0]<<1);
for (auto &x : v) {
dsu.Union(g, x<<1);
dsu.Union(g^1, x<<1^1);
}
dsu.Union(g^1, i<<1);
dsu.Union(g, i<<1^1);
seg.Update(a[v[0]].second, v[0]);
}
seg.Update(a[i].second, i);
}
int ans = 1;
for (int i=0; i<n; i++) {
if (dsu.Find(i<<1) == (i<<1)) {
ans = ans * 2 % mod;
}
}
cout << ans << '\n';
}
Compilation message
port_facility.cpp: In member function 'void SegmentTree::Update(int, int, int, int, int)':
port_facility.cpp:53:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
53 | int mid = s + e >> 1;
| ~~^~~
port_facility.cpp: In member function 'int SegmentTree::Query(int, int, int, int, int)':
port_facility.cpp:61:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
61 | int mid = s + e >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
