#include<bits/stdc++.h>
#define f first
#define s second
#define pii pair<int,int>
using namespace std;
const int N = 1e6 + 5, mod = 1e9 + 7;
int p[N], c[N];
set<pair<int,int>> s[N][2];
set<pii> S;
void rem(int x) {
for(int t = 0; t < 2; t++)
if(s[x][t].size()) S.erase(*s[x][t].begin());
}
void add(int x) {
for(int t = 0; t < 2; t++)
if(s[x][t].size()) S.insert(*s[x][t].begin());
}
void merge(int x, int y) {
if((int)s[p[x]][1].size() + (int)s[p[x]][0].size() < (int)s[p[y]][1].size() + (int)s[p[y]][0].size()) swap(x, y);
int Y = p[y], X = p[x], T = (c[x] == c[y]);
for(int t = 0; t < 2; t++) {
while(s[Y][t].size()) {
pii x = *s[Y][t].begin();
p[x.s] = X; c[x.s] = t ^ T;
s[Y][t].erase(x);
s[X][t ^ T].insert(x);
}
}
}
int main() {
int n;
cin >> n;
vector<pair<int,pair<int,int>> > x;
for(int i = 1; i <= n; i++) {
int l, r;
cin >> l >> r;
x.push_back({l, {r, i}});
x.push_back({r, {0, i}});
s[i][0].insert({r, i});
p[i] = i;
}
sort(x.begin(), x.end());
vector<int> f(n + 2);
for(int i = 0; i < x.size(); i++) {
if(x[i].s.f == 0) {
int id = x[i].s.s, r = x[i].f;
rem(p[id]);
s[p[id]][c[id]].erase({r, id});
add(p[id]);
continue;
}
int r = x[i].s.f, l = x[i].f, id = x[i].s.s;
vector<int> v;
vector<pii> aa;
while(S.size() && (*S.begin()).f < r) {
pii x = *S.begin();
v.push_back(x.s);
if(f[p[x.s]] == i + 1) {
cout << 0;
return 0;
}
f[p[x.s]] = i + 1;
S.erase(x);
aa.push_back(x);
}
while(aa.size()) S.insert(aa.back()), aa.pop_back();
for(int j = 0; j < v.size(); j++) rem(p[v[j]]), merge(v[j], id);
add(p[id]);
}
int ans = 1;
for(int i = 1; i <= n; i++) if(p[i] == i) ans = ans * 2 % mod;
cout << ans;
/*
4
1 2
3 4
5 7
6 8
*/
}
Compilation message
port_facility.cpp: In function 'int main()':
port_facility.cpp:44:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for(int i = 0; i < x.size(); i++) {
| ~~^~~~~~~~~~
port_facility.cpp:68:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for(int j = 0; j < v.size(); j++) rem(p[v[j]]), merge(v[j], id);
| ~~^~~~~~~~~~
port_facility.cpp:52:27: warning: unused variable 'l' [-Wunused-variable]
52 | int r = x[i].s.f, l = x[i].f, id = x[i].s.s;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
94156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
94156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
94156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
94156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
