제출 #518679

#제출 시각아이디문제언어결과실행 시간메모리
518679akhan42Port Facility (JOI17_port_facility)C++17
78 / 100
3903 ms273568 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; const int MX = 1000 * 1000 + 1; 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; set<int> sl[2 * MX]; void init(int n, vi &vals) { this->n = 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, int val, bool is_left) { auto it = sl[v].lower_bound(val); if(is_left) { copy(it, sl[v].end(), back_inserter(nb)); } else { copy(sl[v].begin(), it, back_inserter(nb)); } } 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++, bd, is_left); if(r & 1) add(nb, --r, bd, is_left); } } void del(int p, int val) { for(p += n; p > 0; p >>= 1) sl[p].erase(val); } }; vector<int> att; int ncomps = 0; vi l2r, e2i; vii vlr; Seg seg; int ch(int c) { return c == 1 ? 2 : 1; } void my_push(queue<ii> &q, int node, int color) { int l = vlr[node].F, r = vlr[node].S; seg.del(l, r); seg.del(r, l); 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, e2i[nb], ch(color)); } } } void solve() { int n; cin >> n; l2r.resize(2 * n); e2i.resize(2 * n); att.assign(n, 0); forn(i, n) { int l, r; cin >> l >> r; l--; r--; l2r[l] = r; l2r[r] = l; e2i[l] = e2i[r] = i; vlr.eb(l, r); } seg.init(2 * n, l2r); forn(i, n) { if(!att[i]) { bfs(i); } } stack<int> st[2]; bool bad = false; forn(e, 2 * n) { int i = e2i[e], c = att[i] - 1; if(vlr[i].F == e) { st[c].push(i); } else { if(st[c].top() != i) { bad = true; break; } else { st[c].pop(); } } } cout << (bad ? 0 : mpow(2, ncomps)) << '\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...