#include <bits/stdc++.h>
using namespace std;
const int M = 1 << 20, N = 2*M, INF = 1e9 + 42, MOD = 1e9 + 7;
struct Container {
int deb, fin, id;
};
vector<int> area[2];
vector<Container> ctn;
int n, par[M], deb[M], fin[M], imin[N];
void update(int i, int val) {
i += M;
imin[i] = val;
while(i) {
i >>= 1;
if(deb[imin[i*2]] < deb[imin[i*2+1]])
imin[i] = imin[i*2];
else
imin[i] = imin[i*2+1];
}
}
int getMin(int i, int d, int f, int l, int r) {
if(f <= l || r <= d)
return M-1;
if(l <= d && f <= r)
return imin[i];
int mid = (d + f) >> 1,
ans1 = getMin(i*2, d, mid, l, r),
ans2 = getMin(i*2+1, mid, f, l, r);
if(deb[ans1] < deb[ans2])
return ans1;
return ans2;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
deb[M-1] = INF;
for(int i = 0; i < N; i++)
imin[i] = M-1;
for(int i = 0; i < n; i++)
par[i] = i;
for(int i = 0; i < n; i++) {
cin >> deb[i] >> fin[i];
ctn.push_back({deb[i], fin[i], i});
}
sort(ctn.begin(), ctn.end(),
[](Container a, Container b) {
return a.deb < b.deb;
});
area[0].push_back(INF);
area[1].push_back(INF);
for(int i = 0; i < n; i++) {
for(int j = 0; j < 2; j++)
while(area[j].back() < ctn[i].deb)
area[j].pop_back();
if(area[0].back() < ctn[i].fin && area[1].back() < ctn[i].fin) {
cout << "0\n";
return 0;
}
if(area[0].back() < ctn[i].fin)
area[1].push_back(ctn[i].fin);
else if(area[1].back() < ctn[i].fin)
area[0].push_back(ctn[i].fin);
else if(area[0].back() < area[1].back())
area[0].push_back(ctn[i].fin);
else
area[1].push_back(ctn[i].fin);
}
sort(ctn.begin(), ctn.end(),
[](Container a, Container b) {
return a.fin < b.fin;
});
int nb = n;
for(int i = 0; i < n; i++)
deb[i] = ctn[i].deb, fin[i] = ctn[i].fin;
ctn.clear();
for(int i = 0; i < n; i++)
ctn.push_back({deb[i], fin[i], i});
for(int i = 0; i < n; i++) {
int fi = (int)(lower_bound(fin, fin + n, ctn[i].deb) - fin),
id = getMin(1, 0, M, fi, i);
while(deb[id] < ctn[i].deb) {
deb[ctn[i].id] = min(deb[ctn[i].id], deb[id]);
nb--;
update(id, M-1);
id = getMin(1, 0, M, fi, i);
}
update(i, i);
}
int ans = 1;
for(int i = 0; i < nb; i++)
ans = (ans * 2) % MOD;
cout << ans << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
8532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
8532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
8532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
8532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
