Submission #1177432

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177432		ASN49K	Port Facility (JOI17_port_facility)	C++20	In queue	0 ms	0 KiB

port_facility

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()

std::mt19937 rng(69);
#define UNUSED -1
const int N_MAX=200'000;
const int mod=1e9+7;
bool intersect(std::pair<int,int>a,std::pair<int,int>b)
{
    if(a.first>b.first)
    {
        std::swap(a,b);
    }
    return b.first<=a.second && a.second<=b.second;
}

int viz[N_MAX];
std::vector<int>adj[N_MAX];

void dfs(int nod,int val)
{
    if(viz[nod]!=-1)
    {
        return;
    }
    viz[nod]=val;
    for(auto &c:adj[nod])
    {
        dfs(c,val^1);
    }
}
int main()
{
    //freopen("input.txt","r",stdin);
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int n;
    std::cin>>n;
    std::vector<std::pair<int,int>>a(n);
    for(auto &c:a)
    {
        std::cin>>c.first>>c.second;
    }
    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            if(intersect(a[i] , a[j]))
            {
                //std::cout<<i<<' '<<j<<'\n';
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
        }
    }
    std::fill(viz,viz+n,-1);
    int rez=1;
    for(int i=0;i<n;i++)
    {
        if(viz[i]==-1)
        {
            dfs(i,0);
            rez*=2;
            rez%=mod;
        }
    }
    for(int i=0;i<n;i++)
    {
        for(auto &c:adj[i])
        {
            if(viz[i]==viz[c])
            {
                rez=0;
            }
        }
    }
    std::cout<<rez<<'\n';

    return 0;
}
/*
6 6
1 2 4
1 6 5
4 1
1 1 5
1 1 6
4 5
*/