이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//Be Name Khoda
#include<bits/stdc++.h>
#pragma GCC optmize("Ofast,unroll-loops")
#pragma GCC target ("avx2,tune=native")
using namespace std;
#define ll long long
#define ld long double
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#define pll pair<ll, ll>
#define plll pair<pll, ll>
const ll mxn = 2e6 + 16, md = 1e9 + 7;
ll n, m, q, w;
vector<ll> A, B;
bitset<mxn> mark;
void input() {
cin >> n;
for(int i = 0; i < n; i++) {
cin >> q; q--;
A.push_back(q);
cin >> q; q--;
B.push_back(q);
}
}
struct item {
ll mn, mx, type;
};
struct segtree {
ll sz = 1;
item NE = {mxn, -1, -1};
vector<item> v;
void init(int n) {
while(sz < n) sz <<= 1;
v.assign(2 * sz, NE);
}
void update(int x) {
v[x].mn = min(v[2 * x + 1].mn, v[2 * x + 2].mn);
v[x].mx = max(v[2 * x + 1].mx, v[2 * x + 2].mx);
return;
}
void add_to_mn(int i, pll p, int x, int lx, int rx) {
if(rx - lx == 1) {
v[x].mn = p.first, v[x].type = p.second;
return;
}
int m = (lx + rx) >> 1;
if(i < m) add_to_mn(i, p, 2 * x + 1, lx, m);
else add_to_mn(i, p, 2 * x + 2, m, rx);
v[x].mn = min(v[2 * x + 1].mn, v[2 * x + 2].mn);
return;
}
void add_to_mn(int i, pll p) {
add_to_mn(i, p, 0, 0, sz);
return;
}
void add_to_mx(int i, pll p, int x, int lx, int rx) {
if(rx - lx == 1) {
v[x].mx = p.first, v[x].type = p.second;
return;
}
int m = (lx + rx) >> 1;
if(i < m) add_to_mx(i, p, 2 * x + 1, lx, m);
else add_to_mx(i, p, 2 * x + 2, m, rx);
v[x].mx = max(v[2 * x + 1].mx, v[2 * x + 2].mx);
return;
}
void add_to_mx(int i, pll p) {
add_to_mx(i, p, 0, 0, sz);
return;
}
pll find_mn(int l, int r, int x, int lx, int rx) {
if(rx <= l || r <= lx) return {mxn, -1};
if(rx - lx == 1) {
if(v[x].mn < l - 1) {
return {v[x].mn, v[x].type};
} return {mxn, -1};
}
int m = (lx + rx) >> 1;
if(l <= lx && rx <= r) {
if(v[2 * x + 2].mn < l - 1) {
return find_mn(l, r, 2 * x + 2, m, rx);
} if(v[2 * x + 1].mn < l - 1) {
return find_mn(l, r, 2 * x + 1, lx, m);
} return {mxn, -1};
}
pll p = find_mn(l, r, 2 * x + 2, m, rx);
if(p.first < mxn) return p;
p = find_mn(l, r, 2 * x + 1, lx, m);
return p;
}
pll find_mn(int l, int r) {
return find_mn(l, r, 0, 0, sz);
}
pll find_mx(int l, int r, int x, int lx, int rx) {
if(rx <= l || r <= lx) return {-1, -1};
if(rx - lx == 1) {
if(v[x].mx > r) {
return {v[x].mx, v[x].type};
} return {-1, -1};
}
int m = (lx + rx) >> 1;
if(l <= lx && rx <= r) {
if(v[2 * x + 1].mx > r) {
return find_mx(l, r, 2 * x + 1, lx, m);
} if(v[2 * x + 2].mx > r) {
return find_mx(l, r, 2 * x + 2, m, rx);
} return {-1, -1};
}
pll p = find_mx(l, r, 2 * x + 1, lx, m);
if(p.first > -1) return p;
p = find_mx(l, r, 2 * x + 2, m, rx);
return p;
}
pll find_mx(int l, int r) {
return find_mx(l, r, 0, 0, sz);
}
void set(int i, int x, int lx, int rx) {
if(rx - lx == 1) {
v[x] = NE;
return;
}
int m = (lx + rx) >> 1;
if(i < m) set(i, 2 * x + 1, lx, m);
else set(i, 2 * x + 2, m, rx);
update(x); return;
}
void set(int i) {
set(i, 0, 0, sz);
return;
}
}; segtree st;
inline void BFS(int i) {
vector<ll> bfs; bfs.push_back(i);
ll ptr = 0, x; pll p;
st.set(A[i]), st.set(B[i]);
while(ptr < int(bfs.size())) {
x = bfs[ptr++];
mark.set(x);
p = {0, 0};
while(p.second > -1) {
p = st.find_mx(A[x] + 1, B[x]);
if(p.second == -1 || p.first == -1) break;
bfs.push_back(p.second);
st.set(A[p.second]), st.set(B[p.second]);
} p = {0, 0};
while(p.second > -1) {
p = st.find_mn(A[x] + 1, B[x]);
if(p.second == -1 || p.first == mxn) break;
bfs.push_back(p.second);
st.set(A[p.second]), st.set(B[p.second]);
}
}
return;
}
void solve() {
st.init(2 * n);
for(int i = 0; i < n; i++) {
st.add_to_mn(B[i], {A[i], i});
st.add_to_mx(A[i], {B[i], i});
}
for(int i = 0; i < n; i++) {
pll p, b;
p = st.find_mn(A[i] + 1, B[i]);
b = st.find_mx(A[i] + 1, B[i]);
if(p.first == mxn || b.first == -1) continue;
if(p.second == -1 || b.second == -1) continue;
if(B[p.second] > A[b.second]) {
cout << "0\n";
return;
}
}
ll cnt = 0, ans = 1;
for(int i = 0; i < n; i++) {
if(!mark[i]) {
BFS(i); cnt++;
}
}
for(int i = 0; i < cnt; i++) {
ans <<= 1; ans %= md;
} cout << ans << endl;
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL);
input(), solve();
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
port_facility.cpp:4: warning: ignoring '#pragma GCC optmize' [-Wunknown-pragmas]
4 | #pragma GCC optmize("Ofast,unroll-loops")
|
# | 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... |