Submission #518658

#TimeUsernameProblemLanguageResultExecution timeMemory
518658akhan42Port Facility (JOI17_port_facility)C++17
78 / 100
4131 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(4 * n); build(vals, 1, 0, n - 1); } void build(vii &vals, int v = 1, int tl = 0, int tr = -1) { if(tr == -1) tr = n - 1; if(tl == tr) { sl[v].insert(vals[tl]); return; } int tm = (tl + tr) >> 1; build(vals, 2 * v, tl, tm); build(vals, 2 * v + 1, tm + 1, tr); for(ii e: sl[2 * v]) sl[v].insert(e); for(ii e: sl[2 * v + 1]) sl[v].insert(e); } void query(vi &nb, int L, int R, int bd, bool is_left, int v = 1, int tl = 0, int tr = -1) { if(tr == -1) tr = n - 1; if(L > R) return; if(tl == L && tr == R) { // cerr << "otrezki " << L + 1 << ' ' << R + 1 << '\n'; auto it = sl[v].lower_bound(mp(bd, 0)); 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); } return; } int tm = (tl + tr) >> 1; query(nb, L, min(R, tm), bd, is_left, 2 * v, tl, tm); query(nb, max(L, tm + 1), R, bd, is_left, 2 * v + 1, tm + 1, tr); } void del(int p, ii val, int v = 1, int tl = 0, int tr = -1) { if(tr == -1) tr = n - 1; sl[v].erase(val); if(tl == tr) return; int tm = (tl + tr) >> 1; if(p <= tm) { del(p, val, 2 * v, tl, tm); } else { del(p, val, 2 * v + 1, tm + 1, tr); } } }; vector<int> att; int ncomps = 0; vii l2r, r2l, vlr; Seg segl; 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; segl.del(nodel, {noder, node}); segl.del(noder, {nodel, node}); q.push({node, color}); att[node] = color; } void bfs(int root) { ncomps += 1; // cerr << "Comp: " << ncomps << '\n'; 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(); // cerr << node << ' '; vi nbs; segl.query(nbs, L + 1, R - 1, R, true); segl.query(nbs, L + 1, R - 1, L, false); for(int nb: nbs) { my_push(q, nb, ch(color)); } } // cerr << '\n'; } 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); } segl.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(i, n) { // cerr << att[i] << '\n'; // } 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...