/* Bismillahir Rahmanir Rahim */
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int N = 2000005;
const int oo = 1e9;
struct segtree{
int n;
pii t[N*4];
void init(int _n){
n = _n;
for(int i=0;i<N*4;i++) t[i] = {oo, oo};
}
void update(int b, int e, int node, int pos, int val){
if(b == e){
t[node] = {val, b};
return;
}
int mid = (b + e) / 2, l = 2 * node, h = l + 1;
if(pos <= mid) update(b, mid, l, pos, val);
else update(mid+1, e, h, pos, val);
t[node] = min(t[l], t[h]);
}
void update(int pos, int val){
update(1, n, 1, pos, val);
}
pii query(int b, int e, int node, int x, int y){
if(y < b || e < x) return {oo, oo};
if(b >= x && e <= y) return t[node];
int mid = (b + e) / 2, l = 2 * node, h = l + 1;
return min(query(b, mid, l, x, y), query(mid+1, e, h, x, y));
}
pii query(int x, int y){
return query(1, n, 1, x, y);
}
};
struct dsu{
int n, par[N], en[N], siz[N], vis[N];
void init(int _n){
n = _n;
for(int i=0;i<=n;i++) par[i] = i, siz[i] = 1, en[i] = 0;
}
int Find(int at){
return par[at] == at ? at : par[at] = Find(par[at]);
}
void Union(int a, int b){
a = Find(a), b = Find(b);
if(a == b) return;
if(siz[a] > siz[b]) par[b] = a, siz[a] += siz[b];
else par[a] = b, siz[b] += siz[a];
}
bool isFriend(int a, int b){
if(Find(a) == Find(b)) return true;
else return false;
}
bool isEnemy(int a, int b){
a = Find(a), b = Find(b);
if(Find(en[a]) == Find(b)) return true;
if(Find(en[b]) == Find(a)) return true;
return false;
}
void makeFriend(int a, int b){
a = Find(a), b = Find(b);
if(a == b) return;
if(en[a] && en[b]) Union(en[a], en[b]);
if(!en[a]) en[a] = Find(en[b]);
if(!en[b]) en[b] = Find(en[a]);
Union(a, b);
}
void makeEnemy(int a, int b){
a = Find(a), b = Find(b);
if(a == b) return;
if(!en[a]) en[a] = b;
else Union(en[a], b);
if(!en[b]) en[b] = a;
else Union(en[b], a);
}
int get(){
int ret = 0;
memset(vis, 0, sizeof(vis));
for(int i=1;i<=n;i++){
if(vis[Find(i)]) continue;
vis[Find(i)] = 1;
vis[Find(en[Find(i)])] = 1;
++ret;
}
return ret;
}
};
int n, st[N], en[N], idx[N];
set<int>ms[N];
vector<int>vec[N];
segtree tree;
dsu ds;
int get_prev(int a, int b){
auto it = ms[a].lower_bound(b);
if(it == ms[a].begin()) return 0;
else *(--it);
}
void solve(){
for(int i=2*n;i>=1;i--){
int id = idx[i];
int l = st[id], r = en[id];
if(i == st[id]) continue;
int cur = l;
pii mx = {-1, -1};
while(cur < r){
pii f = tree.query(cur, r);
if(f.first > cur) break;
int pos = f.second, fk = ds.Find(idx[pos]);
if(ds.isFriend(id, fk)){
printf("0\n");
return;
}
mx = max(mx, {ds.siz[fk], fk});
cur = pos + 1;
}
if(mx.first == -1){
tree.update(l, 0);
ms[id].insert(l);
}
else{
cur = l;
int p = get_prev(mx.second, l);
ds.makeEnemy(id, mx.second);
while(cur < r){
pii f = tree.query(cur, r);
if(f.first > cur) break;
int pos = f.second, fk = idx[pos];
if(ds.isEnemy(mx.second, fk)){
printf("0\n");
return;
}
ds.makeFriend(mx.second, fk);
ms[mx.second].insert(pos);
tree.update(pos, p);
p = pos;
cur = pos + 1;
}
tree.update(l, get_prev(ds.Find(id), l));
}
}
int comp = ds.get();
long long ret = 1LL;
long long mod = 1e9 + 7;
for(int i=1;i<=comp;i++){
ret *= 2LL;
ret %= mod;
}
printf("%lld\n", ret);
}
int main(){
scanf("%d", &n);
for(int i=1;i<=n;i++){
scanf("%d %d", &st[i], &en[i]);
idx[st[i]] = i;
idx[en[i]] = i;
}
tree.init(2*n);
ds.init(n);
solve();
return 0;
}
Compilation message
port_facility.cpp: In function 'int get_prev(int, int)':
port_facility.cpp:107:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
port_facility.cpp: In function 'int main()':
port_facility.cpp:166:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
port_facility.cpp:168:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &st[i], &en[i]);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
259864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
259864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
259864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
259864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
