이 제출은 이전 버전의 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;//9:55
ll n, m, q, w;
ll clr[mxn], tp[mxn];
vector<ll> A, B;
bitset<mxn> mark;
void input() {
cin >> n;
for(int i = 0; i < n; i++) {
cin >> q; q--; tp[q] = i;
A.push_back(q);
cin >> q; q--; tp[q] = i;
B.push_back(q);
}
}
struct item {
ll mn, mx, type;
};
struct item2 {
ll n0, n1;
};
struct segtree {
ll sz = 1;
item NE = {mxn, -1, -1};
item2 NE2 = {mxn, mxn};
vector<item> v;
vector<item2> osc;
void init(int n) {
while(sz < n) sz <<= 1;
v.assign(2 * sz, NE);
osc.assign(2 * sz, NE2);
}
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);
osc[x].n0 = min(osc[2 * x + 1].n0, osc[2 * x + 2].n0);
osc[x].n1 = min(osc[2 * x + 1].n1, osc[2 * x + 2].n1);
return;
}
void add(int i, pll p, int x, int lx, int rx) {
if(rx - lx == 1) {
if(p.second == 0) osc[x].n0 = p.first;
else osc[x].n1 = p.first;
return;
}
int m = (lx + rx) >> 1;
if(i < m) add(i, p, 2 * x + 1, lx, m);
else add(i, p, 2 * x + 2, m, rx);
update(x);
}
void add(int i, pll p) {
add(i, p, 0, 0, sz);
return;
}
int SAGZAN(int l, int r, int typ, int x, int lx, int rx) {
if(rx <= l || r <= lx) return mxn;
if(l <= lx && rx <= r) {
if(typ == 0) return osc[x].n0;
return osc[x].n1;
}
int m = (lx + rx) >> 1;
int ans = SAGZAN(l, r, typ, 2 * x + 1, lx, m);
ans = min(ans, SAGZAN(l, r, typ, 2 * x + 2, m, rx));
return ans;
}
int SAGZAN(int l, int r, int typ) {
return SAGZAN(l, r, typ, 0, 0, sz);
}
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;
}
inline void BFS_0(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); clr[p.second] = clr[x] ^ 1;
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); clr[p.second] = clr[x] ^ 1;
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++) {
if(!mark[i]) {
BFS_0(i);
}
} mark.reset();
for(int i = 0; i < n; i++) {
st.add(B[i], {A[i], clr[i]});
}
for(int i = 0; i < n; i++) {
q = st.SAGZAN(A[i] + 1, B[i], clr[i]);
if(q < A[i]) {
cout << "0\n";
return;
}
}
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});
}
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... |