제출 #656019

#제출 시각아이디문제언어결과실행 시간메모리
656019KahouPort Facility (JOI17_port_facility)C++14
10 / 100
44 ms32156 KiB
#include<bits/stdc++.h> using namespace std; #define F first #define S second #define endl '\n' typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int mod = 1e9 + 7; int mul(int a, int b) { return 1ll*a*b%mod; } int pw(int a, int b) { int out = 1; while (b) { if (b&1) out = mul(out, a); a = mul(a,a); b>>=1; } return out; } const int N = 1e6 + 50; int n, L[N], R[N], c[N], cnt; set<pii> sl, sr; bool bad; vector<int> adj[N]; void dfs(int u) { for (int v:adj[u]) { if (!c[v]) { c[v] = 3-c[u]; dfs(v); } else if (c[v] == c[u]) { bad = 1; } } } void solve() { cin >> n; for (int i = 1; i <= n; i++) { cin >> L[i] >> R[i]; sl.insert({L[i], i}); sr.insert({R[i], i}); } while (sr.size()) { int u = sr.begin()->S; sr.erase(sr.begin()); sl.erase({L[u], u}); int prv = 1e9; for (auto it = sl.lower_bound({L[u], 0}); it != sl.end() && it->F < R[u]; it++) { int v = it->S; if (R[v] > prv) { cout << 0 << endl; return; } prv = R[v]; adj[u].push_back(v); adj[v].push_back(u); } } for (int u = 1; u <= n; u++) { if (!c[u]) { c[u] = 1; cnt++; dfs(u); } } cout << pw(2, cnt) << endl; } int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...