Submission #1299175

#TimeUsernameProblemLanguageResultExecution timeMemory
1299175vako_pPort Facility (JOI17_port_facility)C++20
22 / 100
6092 ms3124 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define ff first #define sd second #define debug(x) cerr << #x << " -----> " << x << endl; //#pragma GCC optimize("O3") //#pragma GCC optimize("Ofast") //#pragma GCC optimize("unroll-loops") const int mxN = 1e6 + 5; ll n,mod = 1e9 + 7,val[mxN]; pair<ll,ll> a[mxN]; void dfs(ll at){ for(int i = 0; i < n; i++){ if((a[i].ff < a[at].ff and a[i].sd > a[at].ff and a[i].sd < a[at].sd) or (a[at].ff < a[i].ff and a[at].sd > a[i].ff and a[at].sd < a[i].sd)){ if(val[i]){ if(val[at] == val[i]){ cout << 0; exit(0); } continue; } val[i] = 3 - val[at]; dfs(i); } } } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for(int i = 0; i < n; i++) cin >> a[i].ff >> a[i].sd; sort(a, a + n); // for(int i = 0; i < n; i++) s.pb({a[i].sd, i}); ll ans = 1; for(int i = 0; i < n; i++){ if(val[i]) continue; val[i] = 1; ans = ans * 2 % mod; dfs(i); } cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...