제출 #533904

#제출 시각아이디문제언어결과실행 시간메모리
533904sarePort Facility (JOI17_port_facility)C++17
10 / 100
5 ms2124 KiB
//In the name of Allah :) #include <bits/stdc++.h> using namespace std; string to_string(char c) { return string(1,c); } string to_string(bool b) { return b ? "true" : "false"; } string to_string(const char* s) { return (string)s; } string to_string(string s) { return s; } string to_string(vector<bool> v) { string res = "{"; for(int i = 0; i < (int)v.size(); i++) res += char('0'+v[i]); res += "}"; return res; } template<size_t SZ> string to_string(bitset<SZ> b) { string res = ""; for(size_t i = 0; i < SZ; i++) res += char('0'+b[i]); return res; } template<class A, class B> string to_string(pair<A,B> p); template<class T> string to_string(T v) { // containers with begin(), end() bool fst = 1; string res = "{"; for (const auto& x: v) { if (!fst) res += ", "; fst = 0; res += to_string(x); } res += "}"; return res; } template<class A, class B> string to_string(pair<A,B> p) { return "("+to_string(p.first)+", "+to_string(p.second)+")"; } void DBG() { cerr << "]" << endl; } template<class H, class... T> void DBG(H h, T... t) { cerr << to_string(h); if (sizeof...(t)) cerr << ", "; DBG(t...); } #ifdef LOCAL // compile with -DLOCAL #define wis(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "] : [", DBG(__VA_ARGS__) #else #define wis(...) 0 #endif typedef long long ll; #define int ll #define all(x) (x).begin(), (x).end() const int MAXN = 2e4 + 10, INF = 1e9, MOD = 1e9 + 7; int n; struct SegTree { bool t; int seg[MAXN << 2]; SegTree (bool _t) { t = _t; if (t) { memset(seg, 63, sizeof(seg)); } } int merge (int x, int y) { if (t) { return min(x, y); } return max(x, y); } void update (int nd, int cl, int cr, int ind, int x) { if (cr - cl == 1) { seg[nd] = x; return; } int L = nd << 1, R = L | 1, mid = (cl + cr) >> 1; if (ind < mid) { update(L, cl, mid, ind, x); } else { update(R, mid, cr, ind, x); } seg[nd] = merge(seg[L], seg[R]); } inline void update (int ind, int x) { update(1, 0, n + n, ind, x); } int get (int nd, int cl, int cr, int l, int r) { if (cl == l && cr == r) { return seg[nd]; } int L = nd << 1, R = L | 1, mid = (cl + cr) >> 1, res = t ? INF : 0; if (l < mid) { res = merge(res, get(L, cl, mid, l, min(mid, r))); } if (r > mid) { res = merge(res, get(R, mid, cr, max(l, mid), r)); } return res; } inline int get (int l, int r) { return get(1, 0, n + n, l, r); } } seg1(1), seg2(0); int l[MAXN], r[MAXN], type[MAXN], pw[MAXN], comp; vector<int> adj[MAXN]; vector<pair<int, int>> ver; bitset<MAXN> mark, color; void dfs (int v, bool c) { int u; mark[v] = 1; ver.push_back({l[v], r[v]}); color[v] = c; seg1.update(r[v], INF); seg2.update(l[v], 0); while ((u = seg1.get(l[v], r[v])) < l[v]) { dfs(type[u], c ^ 1); } while ((u = seg2.get(l[v], r[v])) > r[v]) { dfs(type[u], c ^ 1); } } int32_t main() { ios::sync_with_stdio(0); #ifndef LOCAL cin.tie(0); #endif pw[0] = 1; for (int i = 1; i < MAXN; i++) { pw[i] = 2 * pw[i - 1] % MOD; } cin >> n; for (int i = 0; i < n; i++) { cin >> l[i] >> r[i]; type[l[i]] = type[r[i]] = i; seg1.update(r[i], l[i]); seg2.update(l[i], r[i]); } for (int i = 0; i < n; i++) { if (!mark[i]) { comp++; dfs(i, 0); vector<int> tmp, stk[2]; for (auto x : ver) { tmp.push_back(x.first); tmp.push_back(x.second); } ver.clear(); sort(all(tmp)); for (int x : tmp) { int ind = type[x]; if (l[ind] == x) { stk[color[ind]].push_back(ind); } else { if (stk[color[ind]].back() != ind) { cout << 0 << '\n'; return 0; } else { stk[color[ind]].pop_back(); } } } } } cout << pw[comp] << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...