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>
using namespace std;
const int N = 1e6 + 2;
const int mod = 1e9 + 7;
struct st{
int a, b;
}
ar[N];
int n, fen[N + N], p[N], sz[N], col[N];
int t[N * 8];
/*
void upd_sum(int pos){
for(int i = pos; i < N + N; i |= i + 1)
fen[i] ++;
}
int get(int r){
int ret = 0;
for(int i = r; i > 0; i = (i & (i + 1)) - 1)
ret += fen[i];
return ret;
}
int get_sum(int l, int r){
return get(r) - get(l - 1);
}
*/
int f_s(int v){
return (p[v] == v)?v:p[v] = f_s(p[v]);
}
void u_s(int a, int b){
a = f_s(a);
b = f_s(b);
if(a != b){
if(sz[a] < sz[b])
swap(a, b);
p[b] = a;
sz[a] += sz[b];
}
}
void upd_max(int pos, int val, int v = 1, int tl = 1, int tr = 2 * n){
if(tl == tr)
t[v] = val;
else {
int tm = (tl + tr) >> 1;
if(pos <= tm)
upd_max(pos, val, v << 1, tl, tm);
else
upd_max(pos, val, v << 1 | 1, tm + 1, tr);
t[v] = max(t[v << 1], t[v << 1 | 1]);
}
}
int get_max(int l, int r, int v = 1, int tl = 1, int tr = 2 * n){
if(l > tr || tl > r)
return 0;
if(l <= tl && tr <= r)
return t[v];
int tm = (tl + tr) >> 1;
return max(get_max(l, r, v << 1, tl, tm), get_max(l, r, v << 1 | 1, tm + 1, tr));
}
int main(){
cin >> n;
for(int i = 1; i <= n; i ++){
scanf("%d %d", &ar[i].a, &ar[i].b);
p[i] = i, sz[i] = 1;
}
sort(ar + 1, ar + n + 1, [&](st a, st b){
return a.a < b.a;});
for(int i = 1; i <= n; i ++){
/* int cnt = get_sum(ar[i].a, ar[i].b);
if(cnt > 1){
cout << 0 << endl;
return 0;
}
upd_sum(ar[i].b);*/
set <int> s;
for(int j = i - 1; j >= 1; j --){
if(ar[j].b < ar[i].b && ar[i].a < ar[j].b){
s.insert(col[j]);
u_s(j, i);
}
}
/*
if(s.size() == 2){
puts("0");
return 0;
}
if(s.size() == 1){
auto it = *s.begin();
col[i] = 1 - it;
}
* */
/*
int mx = get_max(ar[i].a, ar[i].b);
if(mx > 0){
u_s(i, mx);
}
upd_max(ar[i].b, i);
*/
}
int ans = 1;
for(int i = 1; i <= n; i ++){
if(p[i] == i)
ans = (ans * 2) % mod;
}
cout << ans << endl;
}
Compilation message (stderr)
port_facility.cpp: In function 'int main()':
port_facility.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &ar[i].a, &ar[i].b);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |