Submission #955092

#TimeUsernameProblemLanguageResultExecution timeMemory
955092edogawa_somethingPort Facility (JOI17_port_facility)C++17
22 / 100
4057 ms1048576 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<ll> vii; typedef pair<ll,ll> pii; #define F first #define S second #define pb push_back #define eb emplace_back #define all(v) v.begin(),v.end() #define pow poww const ll M=1e6+10; const ll inf=2e18; const ll mod=1e9+7; ll pow(ll x,ll y){ ll res=1; x%=mod; while(y>0){ if((y&1)) res*=x,res%=mod; x*=x,x%=mod; y=(y>>1); } return res; } ll n,chk; ll vis[M]; pii a[M]; vii v[M]; void dfs(ll x,ll col=1){ vis[x]=col; if(chk==0) return; for(auto it:v[x]){ if(vis[it]==vis[x]){ chk=0; return; } else if(vis[it]==0) dfs(it,3-col); } } int main(){ ios_base::sync_with_stdio(0),cin.tie(0); int TC=1; //cin>>TC; while(TC--){ cin>>n; for(int i=0;i<n;i++){ cin>>a[i].F>>a[i].S; } sort(a,a+n); for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ if(a[i].S>a[j].F&&a[i].S<a[j].S) v[i].pb(j),v[j].pb(i); } } ll ans=1; chk=1; for(int i=0;i<n;i++){ if(vis[i]>0) continue; dfs(i); ans*=2; ans%=mod; ans*=chk; } cout<<ans<<'\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...