제출 #427128

#제출 시각아이디문제언어결과실행 시간메모리
427128kai824Port Facility (JOI17_port_facility)C++17
0 / 100
1 ms332 KiB
#include<bits/stdc++.h> using namespace std; #define int long long //shouldn't need, just in case... int eve[2000005]; list<list<int> > luol; list<int> tmp; int par[1000005],sz[1000005]; int getr(int x){ if(par[x]==-1)return x; return par[x]=getr(par[x]); } bool bruh=false; void merge(int a,int b){ //cout<<"MERGE"<<a<<' '<<b<<'\n'; a=getr(a);b=getr(b); if(a==b){ //cout<<"path1\n"; bruh=true; return; } if(sz[a]<sz[b])swap(a,b); par[b]=a; sz[a]+=sz[b]; } int32_t main(){ ios_base::sync_with_stdio(false);cin.tie(0); int n; cin>>n; int a,b; for(int i=1;i<=n;i++){ cin>>a>>b; eve[a]=i; eve[b]=-i; sz[i]=1;par[i]=-1; } vector<int> st; for(int i=1;i<=n+n;i++){ if(eve[i]>0)st.push_back(eve[i]); else{ for(int j=st.size()-1;j>=0;j--){ if(st[j]==-eve[i]){ st.erase(st.begin()+j); break; } merge(st[j],-eve[i]); } } //for(int x:st)cout<<x<<' ';cout<<'\n'; } if(bruh)cout<<0; else{ int ans=1; for(int i=1;i<=n;i++){ if(par[i]==-1){ ans<<=1; ans%=1000000007ll; } } cout<<ans; } 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...