제출 #533858

#제출 시각아이디문제언어결과실행 시간메모리
533858sarePort Facility (JOI17_port_facility)C++17
0 / 100
29 ms55104 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 all(x) (x).begin(), (x).end() const int MAXN = 2e6 + 10, MOD = 1e9 + 7; int n, 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, int p, bool c) { mark[v] = 1; color[v] = c; ver.push_back({l[v], r[v]}); for (int i : adj[v]) { if (i == p) { continue; } dfs(i, v, c ^ 1); } } int 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 ? 2 * pw[i - 1] - MOD : 2 * pw[i - 1]; } cin >> n; for (int i = 0; i < n; i++) { cin >> l[i] >> r[i]; type[l[i]] = type[r[i]] = i; } auto add_edge = [&](int v, int u) { adj[v].push_back(u); adj[u].push_back(v); }; set<int> s; for (int i = 1; i < n + n; i++) { if (l[type[i]] == i) { s.insert(i); } else { s.erase(l[type[i]]); while (s.size() && *(--s.end()) > l[type[i]]) { add_edge(type[i], type[*(--s.end())]); s.erase(--s.end()); } } } for (int i = 0; i < n; i++) { if (mark[i] == 0) { comp++; dfs(i, -1, 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...