이 제출은 이전 버전의 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;
}
};
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;
}
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++) {
if(tr > r || (tl <= m && v[tl].y < v[tr].y)) {
if(now == -1 || ori[now].y < v[tl].y)
now = v[tl].id;
tv[i] = v[tl];
tl++;
} else {
if(now != -1 && v[tr].x < ori[now].y)
merge(v[tr].id, now);
tv[i] = v[tr];
tr++;
}
}
for(int i = l; i <= r; i++)
v[i] = tv[i];
}
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
int n;
cin >> n;
v.resize(n), tv.resize(n), C.resize(n);
for(int i = 0; i < n; i++) {
C[i] = i;
cin >> v[i].x >> v[i].y;
v[i].id = i;
}
ori = v;
if(!is_vali()) {
cout << "0\n";
return 0;
}
v = ori;
sort(ALL(v));
merge_sort(0, n - 1);
for(int i = 0; i < n; i++) {
v[i].x = n * 2 + 1 - v[i].x;
v[i].y = n * 2 + 1 - v[i].y;
ori[i].x = n * 2 + 1 - ori[i].x;
ori[i].y = n * 2 + 1 - ori[i].y;
}
sort(ALL(v));
merge_sort(0, n - 1);
int ans = 1;
for(int i = 0; i < n; i++)
if(C[i] == i)
ans = (ans << 1) % 1000000007;
cout << ans << '\n';
}
컴파일 시 표준 에러 (stderr) 메시지
port_facility.cpp: In function 'void merge_sort(int, int)':
port_facility.cpp:44:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
44 | 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... |