이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6+15,mod = 1e9+7;
int L[N],R[N];
int par[N],enemy[N];
int find(int a){
if(a==-1)return -1;
if(a==par[a])return a;
return par[a]= find(par[a]);
}
void make_enemy(int a,int b){
a = find(a),b = find(b);
int u = find(enemy[a]), v = find(enemy[b]);
if(a==b || (u!=-1 && u==v)){
printf("0\n");
exit(0);
}
if(v!=-1)par[v]= a;
if(u!=-1)par[u]= b;
enemy[a]= b;
enemy[b]= a;
}
int main(){
//freopen("input.txt","r",stdin);
int n;
cin>>n;
vector<pair<int,int> >v;
for(int i=1;i<=n;++i){
scanf("%d%d",&L[i],&R[i]);
v.push_back(make_pair(L[i],i));
}
sort(v.begin(),v.end());
for(int i=1;i<=n;++i)par[i]= i,enemy[i]= -1;
set<pair<int,int> >s;
set<pair<int,int> >::iterator it,jt;
int u;
for(int i=0;i<v.size();++i){
int l = v[i].first, id = v[i].second;
while(!s.empty()){
it = s.begin();
if( (*it).first<l)s.erase(it);
else
break;
}
pair<int,int> last= make_pair(-1,-1);
bool is = 0;
for(it = s.lower_bound(make_pair(l,0));it!= s.end();){
if( (*it).first<=R[id]){
u = (*it).second;
make_enemy(u,id);
last = *it;
jt = it;
++jt;
s.erase(it);
it = jt;
is = 1;
}
else
break;
}
if(is)
s.insert(last);
s.insert(make_pair(R[id],id));
}
long long ret= 1;
for(int i=1;i<=n;++i){
if(find(i)==i&& find(enemy[i])<i){
ret= (ret*2)%mod;
}
}
cout<<ret<<endl;
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
port_facility.cpp: In function 'int main()':
port_facility.cpp:50:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v.size();++i){
~^~~~~~~~~
port_facility.cpp:41:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&L[i],&R[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |