This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define N 1000005
#define pii pair<int,int>
#define xx first
#define yy second
#define MOD 1000000007
#define pb push_back
using namespace std;
typedef long long ll;
ll mul(ll x, ll y){
return (x*y)%MOD;
}
ll power(ll x, ll y){
if(y == 0)return 1;
ll pola = power(x, y/2);
pola = mul(pola, pola);
if(y%2 == 1)pola = mul(pola, x);
return pola;
}
int n;
pii niz[2 * N];
int levo[N];
int desno[N];
pii par[N];
struct cvor{
int najm;
int najv;
int p1;
int p2;
};
cvor spoji(cvor a, cvor b){
cvor c = a;
if(b.najm < c.najm){
c.najm = b.najm;
c.p1 = b.p1;
}
if(b.najv > c.najv){
c.najv = b.najv;
c.p2 = b.p2;
}
return c;
}
cvor seg[8 * N];
void init(int node, int l, int r){
if(l == r){
seg[node] = {niz[l].xx, niz[l].xx, niz[l].yy, niz[l].yy};
return;
}
int mid = (l + r) / 2;
init(node * 2, l, mid);
init(node * 2 + 1, mid + 1, r);
seg[node] = spoji(seg[node * 2], seg[node * 2 + 1]);
}
cvor query(int node, int l, int r, int levo, int desno){
if(l > r || levo > desno || levo > r || l > desno)return {(int)1e9, 0, -1, -1};
if(l >= levo && r <= desno)return seg[node];
int mid = (l + r) / 2;
return spoji(query(node*2,l,mid,levo,desno), query(node*2+1,mid+1,r,levo,desno));
}
int br;
int boja[N];
vector<int> graf[N];
void dfs(int x, int y){
boja[x] = y;
for(auto c:graf[x]){
if(boja[c] == -1)dfs(c,y^1);
else if(boja[c] == y){
cout << 0 << "\n";
exit(0);
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin >> n;
ff(i,1,n){
int x,y;
cin >> x >> y;
par[i] = {x,y};
niz[x] = {y,i};
niz[y] = {x,i};
}
init(1,1,2*n);
ff(i,1,n){
if(par[i].xx + 1 == par[i].yy)continue;
cvor sta = query(1,1,2*n,par[i].xx + 1,par[i].yy - 1);
if(sta.najm < par[i].xx){
//levo[i] = sta.p1;
graf[i].pb(sta.p1);
graf[sta.p1].pb(i);
}
if(sta.najv > par[i].yy){
graf[i].pb(sta.p2);
graf[sta.p2].pb(i);
}
}
// cout << "\n";
// ff(i,1,n){
// cout << levo[i] << " " << desno[i] << "\n";
// }
// cout << "\n\n";
ff(i,1,n)boja[i] = -1;
ff(i,1,n){
if(boja[i] == -1){
br++;
dfs(i,0);
}
}
cout << power(2, br) << "\n";
return 0;
}
Compilation message (stderr)
port_facility.cpp: In function 'int main()':
port_facility.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
| ^
port_facility.cpp:91:5: note: in expansion of macro 'ff'
91 | ff(i,1,n){
| ^~
port_facility.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
| ^
port_facility.cpp:101:5: note: in expansion of macro 'ff'
101 | ff(i,1,n){
| ^~
port_facility.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
| ^
port_facility.cpp:119:5: note: in expansion of macro 'ff'
119 | ff(i,1,n)boja[i] = -1;
| ^~
port_facility.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
| ^
port_facility.cpp:120:5: note: in expansion of macro 'ff'
120 | ff(i,1,n){
| ^~
# | 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... |