이 제출은 이전 버전의 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;
bool operator<(const datas &a) const {
return x < a.x;
}
};
vector<datas> ori;
vector<int> e[1000100];
int n, v[1000100], tv[1000100], sz[2000100], C[2000100];
inline int find(int a) {
return C[a] != a ? C[a] = find(C[a]) : a;
}
inline int max(int a, int b) {
return a < b ? b : a;
}
inline void swap(int &a, int &b) {
a ^= b, b ^= a, a ^= b;
}
inline void merge(int a, int b) {
(a = find(a)) != (b = find(b)) && (sz[a] < sz[b] && (swap(a, b), 1), sz[a] += sz[b], C[b] = a);
}
void merge_sort(int l, int r) {
if (l == r)
return;
int m = l+r >> 1, tl = l, tr = m + 1, now = -1;
merge_sort(l, m), merge_sort(m + 1, r);
for (int i = l; i <= r; ++i)
tr > r || (tl <= m && ori[v[tl]].y < ori[v[tr]].y) ? (now == -1 || ori[now].y < ori[v[tl]].y) && (now = v[tl]), tv[i] = v[tl++] : (now != -1 && ori[v[tr]].x < ori[now].y && (e[v[tr]].pb(now), e[now].pb(v[tr]), merge(v[tr], now + n), merge(now, v[tr] + n), 1), tv[i] = v[tr++]);
// for(int i = l; i <= r; i++)
// v[i] = tv[i];
memcpy(v + l, tv + l, sizeof(int) * (r - l + 1));
}
int vis[1000100];
vector<int> lv, rv;
inline void dfs(int a, int c) {
++vis[a], (c ? rv : lv).pb(a);
for(int i : e[a])
vis[i] || (dfs(i, ~c), 0);
}
inline bool f(int a, int b) {
return ori[a].x < ori[b].x;
}
int main() {
Tie
cin >> n;
ori.resize(n);
for(int i = 0; i < n; ++i)
cin >> ori[i].x >> ori[i].y;
for(int i = 0; i < (n<<1); ++i)
C[i] = i, sz[i] = 1;
for(int i = 0; i < n; ++i)
v[i] = i;
sort(v, v + n, f), merge_sort(0, n - 1);
for (int i = 0; i < n; ++i)
ori[i].x = (n<<1|1) - ori[i].x, ori[i].y = (n<<1|1) - ori[i].y, swap(ori[i].x, ori[i].y);
for (int i = 0; i < n; ++i)
v[i] = i;
sort(v, v + n, f), merge_sort(0, n - 1);
int ans = 1;
for (int i = 0; i < n; ++i) {
if (!vis[i]) {
lv.clear(), rv.clear(), dfs(i, 0);
sort(ALL(lv), f);
int mx = -1;
for (int j : lv) {
if(ori[j].x < mx && mx < ori[j].y) {
cout << "0\n";
return 0;
}
mx = max(mx, ori[j].y);
}
sort(ALL(rv), f);
mx = -1;
for (int j : rv) {
if (ori[j].x < mx && mx < ori[j].y) {
cout << "0\n";
return 0;
}
mx = max(mx, ori[j].y);
}
}
}
for (int i = 0; i < n; ++i)
if (find(i) == find(i + n)) {
cout << "0\n";
return 0;
}
int tmp = 0;
for (int i = 0; i < (n<<1); ++i)
find(i) == i && ++tmp;
tmp >>= 1;
for(int i = 0; i < tmp; ++i)
ans <<= 1, ans %= 1000000007;
cout << ans << '\n';
}
컴파일 시 표준 에러 (stderr) 메시지
port_facility.cpp: In function 'void merge(int, int)':
port_facility.cpp:43:92: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
43 | (a = find(a)) != (b = find(b)) && (sz[a] < sz[b] && (swap(a, b), 1), sz[a] += sz[b], C[b] = a);
| ~~~~~^~~
port_facility.cpp: In function 'void merge_sort(int, int)':
port_facility.cpp:49:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
49 | int m = l+r >> 1, tl = l, tr = m + 1, now = -1;
| ~^~
# | 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... |