Submission #1177563

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177563		ASN49K	Port Facility (JOI17_port_facility)	C++20	22 / 100	6091 ms	21320 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;
using i64=long long;


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);
            }
        }
    }
    int rez=1;
    std::vector<i64>cash(2*n+1);
    for(auto &c:a)
    {
        cash[c.first]=cash[c.second]=rng();
    }
    std::set<int>mp;
    mp.insert(0);

    for(int i=1;i<=2*n;i++)
    {
        cash[i]^=cash[i-1];
        if(mp.count(cash[i]))
        {
             rez*=2;
             rez%=mod;
        }
        mp.insert(cash[i]);
    }



    std::fill(viz,viz+n,-1);
    for(int i=0;i<n;i++)
    {
        if(viz[i]==-1)
        {
            dfs(i,0);
        }
    }
    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;
}

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 0 / 56
• Subtask 4: 0 / 22