제출 #990375

#제출 시각아이디문제언어결과실행 시간메모리
990375LOLOLOPort Facility (JOI17_port_facility)C++14
22 / 100
1917 ms1048576 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define f first #define s second #define pb push_back #define ep emplace #define eb emplace_back #define lb lower_bound #define ub upper_bound #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin()) #define mem(f,x) memset(f , x , sizeof(f)) #define sz(x) (ll)(x).size() #define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b)) #define mxx *max_element #define mnn *min_element #define cntbit(x) __builtin_popcountll(x) #define len(x) (int)(x.length()) const int N = 2e6 + 10; int id[N], col[N], cc = 0; vector <int> ed[N]; void dfs(int u) { for (auto x : ed[u]) { if (col[x] == -1) { col[x] = 1 - col[u]; dfs(x); } if (col[u] == col[x]) { cc = 1; } } } ll solve() { mem(col, -1); vector <pair <int, int>> seg; int n; cin >> n; for (int i = 1; i <= n; i++) { int a, b; cin >> a >> b; seg.pb({a, b}); } sort(all(seg)); set <int> save; for (int i = 0; i < n; i++) { id[seg[i].f] = id[seg[i].s] = i; auto it = save.lower_bound(seg[i].f); while (it != save.end() && *it < seg[i].s) { ed[i].pb(id[*it]); ed[id[*it]].pb(i); it = next(it); } save.insert(seg[i].s); } int cnt = 0; for (int i = 0; i < n; i++) { if (col[i] == -1) { col[i] = 0; dfs(i); cnt++; } } if (cc) return 0; ll ans = 1, mod = 1e9 + 7; for (int i = 1; i <= cnt; i++) { ans = (ans + ans) % mod; } return ans; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; //cin >> t; while (t--) { cout << solve() << '\n'; } 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...