제출 #518666

#제출 시각아이디문제언어결과실행 시간메모리
518666akhan42Port Facility (JOI17_port_facility)C++17
78 / 100
3960 ms1048580 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; #define F first #define S second #define forn(i, n) for(int i = 0; i < n; ++i) #define forbn(i, b, n) for(int i = b; i < n; ++i) #define sz(v) (int)v.size() #define pb push_back #define eb emplace_back #define all(v) v.begin(), v.end() #define mp make_pair #define at(m, p) (m.find(p) != m.end() ? m[p] : 0) typedef pair<int, int> ii; typedef vector<int> vi; typedef vector<ii> vii; typedef long long ll; typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; template <class T> inline void mineq(T &a, T b) { a = min(a, b); } template <class T> inline void maxeq(T &a, T b) { a = max(a, b); } const long long mod = 1000 * 1000 * 1000 + 7; inline long long mpow(long long b, long long ex) { long long r = 1; while(ex) { if(ex & 1) r = (r * b) % mod; ex = ex >> 1; b = (b * b) % mod; } return r; } struct Seg { int n; vector<set<ii>> sl; void init(int n, vii &vals) { this->n = n; sl.resize(2 * n); forn(i, n) { sl[i + n].insert(vals[i]); } for(int i = n - 1; i > 0; i--) { sl[i].insert(all(sl[2 * i])); sl[i].insert(all(sl[2 * i + 1])); } } void add(vi &nb, int v, ii val, bool is_left) { auto it = sl[v].lower_bound(val); if(is_left) { for(; it != sl[v].end(); it++) nb.pb(it->S); } else { for(auto it2 = sl[v].begin(); it2 != it; it2++) nb.pb(it2->S); } } void query(vi &nb, int l, int r, int bd, bool is_left) { for(l += n, r += n + 1; l < r; l >>= 1, r >>= 1) { if(l & 1) add(nb, l++, mp(bd, 0), is_left); if(r & 1) add(nb, --r, mp(bd, 0), is_left); } } void del(int p, ii val) { for(p += n; p > 0; p >>= 1) sl[p].erase(val); } }; vector<int> att; int ncomps = 0; vii l2r, vlr; Seg seg; int ch(int c) { return c == 1 ? 2 : 1; } void my_push(queue<ii> &q, int node, int color) { int nodel = vlr[node].F, noder = vlr[node].S; seg.del(nodel, {noder, node}); seg.del(noder, {nodel, node}); q.push({node, color}); att[node] = color; } void bfs(int root) { ncomps += 1; queue<ii> q; my_push(q, root, 1); while(!q.empty()) { int node = q.front().F, color = q.front().S; int L = vlr[node].F, R = vlr[node].S; q.pop(); vi nbs; seg.query(nbs, L + 1, R - 1, R, true); seg.query(nbs, L + 1, R - 1, L, false); for(int nb: nbs) { my_push(q, nb, ch(color)); } } } void solve() { int n; cin >> n; l2r.resize(2 * n); att.assign(n, 0); forn(i, n) { int l, r; cin >> l >> r; l--; r--; l2r[l] = mp(r, i); l2r[r] = mp(l, i); vlr.eb(l, r); } seg.init(2 * n, l2r); forn(i, n) { if(!att[i]) { bfs(i); } } vector<array<int, 3>> v[2]; forn(i, n) { int l = vlr[i].F, r = vlr[i].S; v[att[i] - 1].pb({l, 0, i}); v[att[i] - 1].pb({r, 1, i}); } sort(all(v[0])); sort(all(v[1])); bool bad = false; forn(c, 2) { stack<int> st; for(auto ar: v[c]) { int op = ar[1], ind = ar[2]; if(op == 0) { st.push(ind); } else { int ind_left = st.top(); if(ind_left != ind) { bad = true; break; } else { st.pop(); } } } } if(!bad) { cout << mpow(2, ncomps) << '\n'; } else { cout << 0 << '\n'; } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); // freopen("gathering.in", "r", stdin); // freopen("gathering.out", "w", stdout); int t = 1; // cin >> t; while(t--) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...