이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000005;
const int mod = 1e9 + 7;
int n, ans = 1;
int dsu[2 * MAXN];
pair <int, int> A[MAXN];
map <int, int> M;
int Root(int node)
{
return dsu[node] == node ? node : dsu[node] = Root(dsu[node]);
}
void Union(int x, int y)
{
x = Root(x);
y = Root(y);
if(x == y)
{
return;
}
dsu[x] = y;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> A[i].first >> A[i].second;
dsu[i] = i;
dsu[i + n] = i + n;
}
sort(A + 1, A + n + 1);
for(int i = 1; i <= n; i++)
{
map <int, int> :: iterator it1 = M.lower_bound(A[i].first);
map <int, int> :: iterator it2 = M.lower_bound(A[i].second);
while(it1 != it2)
{
Union(i, it1->second + n);
Union(i + n, it1->second);
if(Root(i) == Root(i + n))
{
cout << 0 << '\n';
return 0;
}
if(Root(it1->second) == Root(it1->second + n))
{
cout << 0 << '\n';
return 0;
}
int id = prev(it2)->second;
if(Root(id) == Root(it1->second))
{
break;
}
it1++;
}
M[A[i].second] = i;
}
for(int i = 1; i <= n; i++)
{
if(Root(i) == i)
{
ans = ans * 2 % mod;
}
}
cout << ans << '\n';
}
# | 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... |