# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
59898 | babo | Port Facility (JOI17_port_facility) | C++14 | 3577 ms | 219716 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define L long long
#define mod 1000000007
using namespace std;
struct S{
L s,e,ord;
}a[1000010];
bool operator<(S a,S b){
return a.e<b.e;
}
bool cmps(S a,S b){
return a.s<b.s;
}
bool cmpe(S a,S b){
return a.e<b.e;
}
L n,ans=1;
L color[1000010];
vector<L>v[1000010];
void dfs(L x){
L i;
for(i=0;i<v[x].size();i++)
{
if(!color[v[x][i]])
{
color[v[x][i]]=3-color[x];
dfs(v[x][i]);
}
}
}
bool ok(){
L i;
stack<L>s1,s2;
for(i=1;i<=n;i++)
{
if(color[a[i].ord]==1)
{
while(!s1.empty()&&s1.top()<a[i].s) s1.pop();
if(!s1.empty()&&s1.top()<a[i].e) return 0;
s1.push(a[i].e);
}
else
{
while(!s2.empty()&&s2.top()<a[i].s) s2.pop();
if(!s2.empty()&&s2.top()<a[i].e) return 0;
s2.push(a[i].e);
}
}
return 1;
}
int main()
{
scanf("%lld",&n);
L i;
for(i=1;i<=n;i++)
{
scanf("%lld %lld",&a[i].s,&a[i].e);
a[i].ord=i;
}
sort(a+1,a+n+1,cmps);
set<S>st;
for(i=1;i<=n;i++)
{
set<S>::iterator it=st.lower_bound((S){a[i].e,a[i].s});
while(it!=st.end()&&it->e<a[i].e)
{
v[a[i].ord].push_back(it->ord);
v[it->ord].push_back(a[i].ord);
st.erase(it);
it=st.lower_bound((S){a[i].e,a[i].s});
}
st.insert(a[i]);
}
while(!st.empty())
{
st.erase(st.begin());
}
for(i=1;i<=n;i++)
{
a[i].e*=-1;
a[i].s*=-1;
swap(a[i].s,a[i].e);
}
sort(a+1,a+n+1,cmps);
while(!st.empty())
{
st.erase(st.begin());
}
for(i=1;i<=n;i++)
{
set<S>::iterator it=st.lower_bound((S){a[i].e,a[i].s});
while(it!=st.end()&&it->e<a[i].e)
{
v[a[i].ord].push_back(it->ord);
v[it->ord].push_back(a[i].ord);
st.erase(it);
it=st.lower_bound((S){a[i].e,a[i].s});
}
st.insert(a[i]);
}
for(i=1;i<=n;i++)
{
a[i].e*=-1;
a[i].s*=-1;
swap(a[i].s,a[i].e);
}
sort(a+1,a+n+1,cmps);
for(i=1;i<=n;i++)
{
if(!color[i])
{
ans*=2;
ans%=mod;
color[i]=1;
dfs(i);
}
//printf("%lld ",color[i]);
}
if(!ok()) printf("%lld",0);
else printf("%lld",ans);
}
Compilation message (stderr)
# | 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... |