#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;
const int mod = 1e9 + 7;
int mul(int a, int b) { return (a * 1ll * b) % mod; }
struct bod
{
int x, y, i;
};
vector<bod> a;
vector<int> col;
struct segment_tree2d
{
int n2 = 1;
vector<vector<int> > st;
vector<int> l, r;
void initialize(int n)
{
while (n2 <= n) n2 <<= 1;
st.assign(n2 * 2, {}), l.assign(n2 * 2, -1), r.assign(n2 * 2, -1);
for (int i = n2; i < n2 * 2; i++) l[i] = r[i] = i - n2;
for (int i = n2 - 1; i > 0; i--) l[i] = l[i * 2], r[i] = r[i * 2 + 1];
}
void add(int x, int i, int vr = 1)
{
if (x < l[vr] || x > r[vr]) return;
st[vr].push_back(i);
if (x == l[vr] && r[vr] == x) return;
add(x, i, vr * 2), add(x, i, vr * 2 + 1);
}
void query(int x1, int x2, int y1, int y2, int c, set<pair<int, int> > &q, int vr = 1)
{
if (x2 < l[vr] || r[vr] < x1) return;
if (x1 <= l[vr] && r[vr] <= x2)
{
while (!st[vr].empty() && x1 <= a[st[vr].back()].x && a[st[vr].back()].x <= x2 && y1 <= a[st[vr].back()].y && a[st[vr].back()].y <= y2)
{
if (col[a[st[vr].back()].i] == -1)
{
q.insert({ a[st[vr].back()].x, st[vr].back() });
col[a[st[vr].back()].i] = c;
}
st[vr].pop_back();
}
return;
}
query(x1, x2, y1, y2, c, q, vr * 2);
query(x1, x2, y1, y2, c, q, vr * 2 + 1);
}
};
bool cmpxs(bod a, bod b) { return a.y < b.y; }
bool cmpys(bod a, bod b) { return a.x > b.x; }
bool cmpi(bod a, bod b) { return a.i < b.i; }
segment_tree2d xs, ys;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
xs.initialize(n), ys.initialize(n);
a.resize(n), col.resize(n, -1);
vector<int> id(2 * n);
for (int i = 0; i < n; i++) cin >> a[i].x >> a[i].y, a[i].i = i, id[--a[i].x] = id[--a[i].y] = i;
sort(a.begin(), a.end(), cmpxs);
for (bod i : a) xs.add(i.x, i.i);
sort(a.begin(), a.end(), cmpys);
for (bod i : a) ys.add(i.y, i.i);
sort(a.begin(), a.end(), cmpi);
set<pair<int, int> > ns, qu;
for (int i = 0; i < n; i++) ns.insert({ a[i].x, a[i].i });
int ans = 1, c = 0;
while (!ns.empty())
{
int i = ns.begin()->second;
qu.insert({ a[i].x, i }); col[i] = c;
while (!qu.empty())
{
int j = qu.begin()->second;
ns.erase(*qu.begin()), qu.erase(qu.begin());
xs.query(a[j].x, a[j].y, a[j].y, 2 * n, col[j] ^ 1, qu);
ys.query(0, a[j].x, a[j].x, a[j].y, col[j] ^ 1, qu);
}
ans = mul(ans, 2), c += 2;
}
vector<vector<int> > v(c * 2);
for (int i = 0; i < 2 * n; i++)
{
if (!v[col[id[i]]].empty() && v[col[id[i]]].back() == id[i]) v[col[id[i]]].pop_back();
else v[col[id[i]]].push_back(id[i]);
}
for (int i = 0; i < c * 2; i++) if (!v[i].empty())
{
cout << "0\n";
return 0;
}
cout << ans << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
