| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 656049 | aebov | Port Facility (JOI17_port_facility) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("Ofast")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#pragma GCC optimize("unroll-loops") #include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<utility>
#include<set>
#define ll long long
#define ln (e-s+1)
#define md ((s+e)/2)
#define dm ((e+s)/2+1)
#define lc (id*2)
#define rc (id*2+1)
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll , ll>
#define F first
#define S second
using namespace std;
const int N = 1e6 + 5;
const ll mod = (ll)1e9 + 7;
int n, a[N], b[N], cnt;
ll int ans = 1LL;
bool vis[N];
vector<pii> vc[2];
set<int> st;
pii segmin[N << 2], seg[2][N << 2];
void upd(int ind, int p, pii x, int id = 1,int s = 0, int e = (n<<1)){
if(e - s == 1){
seg[ind][id] = x;
return;
}
if(p < md)upd(ind, p, x, lc , s, md);
else upd(ind, p, x, rc, md, e);
seg[ind][id] = min(seg[ind][lc], seg[ind][rc]);
}
/*void updmax(int p, pii x, int id = 1,int s = 1, int e = (n<<1) + 1){
if(p < s || p > e)return;
if(ln == 1){
segmax[id] = x;
return;
}
updmax(p, x, lc, s, md), updmax(p, x, rc, dm , e);
segmax[id] = max(segmax[lc], segmax[rc]);
}*/
pii get(int ind, int l,int r,int id = 1,int s = 0, int e = (n<<1)){
if(l >= e|| r <= s)return {mod, mod};
if(l <=s&& e<= r)return seg[ind][id];
return min(get(ind ,l, r, lc, s, md), get(ind, l, r, rc, md, e));
}
/*pii getmax(int l,int r,int id = 1,int s = 1, int e = (n<<1) + 1){
if(l > e|| r < s)return {-mod, -mod};
if(l <=s&& e<= r)return segmax[id];
return max(getmax(l, r, lc, s, md), getmax(l, r, rc, dm, e));
}*/
void dfs(int v,int c){
// cout << "dfs " << v << " " << c << endl;
vis[v] = true;
upd(0, b[v],{mod, v});
upd(1, a[v],{mod, v});
vc[c].pb({a[v], b[v]});
while(true){
auto p = get(0, a[v], b[v]);
if(p.F > a[v])break;
dfs(p.S, c ^ 1);
}
while(true){
auto p = get(1 ,a[v], b[v]);
if(-p.F < b[v])break;
dfs(p.S, c ^ 1);
}
}
bool valid(vector<pii> vc){
st.clear();
sort(vc.begin(), vc.end());
for(pii i : vc){
auto it = st.lower_bound(i.F);
if(it != st.end() && (*it) <= i.S){
printf("%d\n", 0);
exit(0);
}
st.insert(i.S);
}
return 0;
}
int main(){
scanf("%d",&n);
fill(seg[0] , seg[0] + N * 4 , pii(mod, mod));
fill(seg[1] , seg[1] + N * 4 , pii(mod , mod));
for(int i = 0; i < n; i ++){
scanf("%d%d", &a[i], &b[i]); a[i]--, b[i]--;
upd(0, b[i], {a[i], i}), upd(1, a[i], {-b[i],i});
}
for(int i = 0; i < n; i ++) if(!vis[i])dfs(i, 0), cnt ++;
if(valid(vc[0]) || valid(vc[1]))return 0;
while(cnt --) ans <<= 1, ans %= mod;
printf("%lld\n", ans);
}