이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define long long long
using namespace std;
const long MOD = 1e9+7;
const int N = 1 << 21;
struct seg {
int l, r, i;
seg() { l = r = i = MOD; }
seg(int l, int r, int i): l(l), r(r), i(i) {}
seg(int r): r(r) { l = i = MOD; }
bool operator<(const seg& rhs) const { return r < rhs.r; }
};
int n;
vector<seg> a;
set<seg> st;
int dsu[N];
int root(int v) { return (dsu[v] < 0 ? v : dsu[v] = root(dsu[v])); }
void merge(int u, int v) {
if((u = root(u)) == (v = root(v))) return;
dsu[u] += dsu[v];
dsu[v] = u;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for(int i = 0, x, y; i < n; i++) {
cin >> x >> y;
a.emplace_back(x, y, i);
}
fill(dsu, dsu+N, -1);
sort(a.begin(), a.end(), [] (seg x, seg y) { return x.l < y.l; });
for(seg s: a) {
while(!st.empty() && st.begin()->r < s.l) st.erase(st.begin());
auto ed = st.upper_bound(seg(s.r));
if(st.empty() || ed == st.begin()) {
st.insert(s);
continue;
}
for(auto it = st.begin(); it != ed; it++) {
int u = s.i, v = it->i;
merge(u, v + n);
merge(u + n, v);
if(root(v) == root(prev(ed)->i+ n)) break;
}
st.insert(s);
}
for(int i = 0; i < n; i++) if(root(i) == root(i + n)) cout << 0, exit(0);
long ans = 1;
for(int i = 0; i < n; i++) if(root(i) == i) ans = ans * 2 % MOD;
cout << ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |