제출 #990829

#제출 시각아이디문제언어결과실행 시간메모리
990829prvocisloPort Facility (JOI17_port_facility)C++17
0 / 100
1 ms348 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...