이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optimize ("Ofast","unroll-loops")
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define MP make_pair
#define F first
#define S second
#define setpre(a) cout.precision(a),cout<<fixed;
#define ALL(a) a.begin(),a.end()
#define MEM(a,b) memset(a,b,sizeof a)
#define Tie ios::sync_with_stdio(0),cin.tie(0);
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
struct datas {
int x, y, id;
bool operator<(const datas &a) {
return x < a.x;
}
};
int n;
vector<datas> ori, v, tv;
vector<int> C;
int find(int a) {
if(C[a] != a) return C[a] = find(C[a]);
return a;
}
void merge(int a, int b) {
// cout << a << ' ' << b << '\n';
a = find(a);
b = find(b);
if(a == b) return;
C[a] = b;
}
// bool is_vali() {
// sort(ALL(v));
// stack<int> st1, st2;
// for(datas &i : v) {
// while(!st1.empty() && st1.top() < i.x)
// st1.pop();
// while(!st2.empty() && st2.top() < i.x)
// st2.pop();
// if(st1.empty() || st1.top() > i.y)
// st1.push(i.y);
// else if(st2.empty() || st2.top() > i.y)
// st2.push(i.y);
// else
// return 0;
// }
// return 1;
// }
int main() {Tie
cin >> n;
v.resize(n), C.resize(n * 2);
for(int i = 0; i < n; i++) {
cin >> v[i].x >> v[i].y;
v[i].id = i;
}
for(int i = 0; i < n * 2; i++)
C[i] = i;
ori = v;
// if(!is_vali()) {
// cout << "0\n";
// return 0;
// }
v = ori;
sort(ALL(v));
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(v[i].x < v[j].x && v[i].y < v[j].y && v[j].x < v[i].y) {
merge(i, j + n);
merge(i + n, j);
}
}
}
int ans = 1;
for(int i = 0; i < n; i++)
if(find(i) == find(i + n))
ans = 0;
for(int i = 0; i < n; i++)
if(find(i) == i)
ans = (ans << 1) % 1000000007;
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... |