# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
59899 | babo | Port Facility (JOI17_port_facility) | C++14 | 29 ms | 23800 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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);
}
컴파일 시 표준 에러 (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... |