Submission #1178604

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178604		ASN49K	Port Facility (JOI17_port_facility)	C++20	22 / 100	160 ms	42144 KiB

port_facility

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define LOCAL 0
std::mt19937_64 rng(6994031);
#define UNUSED -1
const int N_MAX=1'000'000;
const int mod=1e9+7;
using i64=long long;
int viz[N_MAX];
std::vector<int>adj[N_MAX];
struct Aib
{
    int n;
    std::vector<int>maxx;
    int lsb(int x)
    {
        return x&(-x);
    }
    void update(int poz,int val)
    {
        for(int i=poz;i<=n;i+=lsb(i))
        {
            maxx[i]=std::max(maxx[i] , val);
        }
    }
    int query(int poz)
    {
        int rez=0;
        for(int i=poz;i>0;i-=lsb(i))
        {
            rez=std::max(rez , maxx[i]);
        }
        return rez;
    }
    void init(int n)
    {
        this->n=n;
        maxx=std::vector<int>(n+1,0);
    }
};


struct interval
{
    int l,r,rezl,rezr,index;
};
void dfs(int nod,int val)
{
    if(viz[nod]!=-1)
    {
        return;
    }
    viz[nod]=val;
    for(auto &c:adj[nod])
    {
        dfs(c,val^1);
    }
}
signed main()
{
    #if LOCAL
        auto __file = freopen("input.txt","r",stdin);
    #endif
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int n;
    std::cin>>n;
    for(int i=0;i<n;i++)
    {
        adj[i].clear();
        viz[i]=-1;
    }
    std::vector<interval>a(n);
    std::vector<i64>cash(2*n+1);
    int idk=0;
    for(auto &c:a)
    {
        std::cin>>c.l>>c.r;
        cash[c.l]=cash[c.r]=rng();
        c.index=idk++;
    }


    int rez=1;
    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::sort(all(a) , [&](interval x,interval y){
       return x.l<y.l;
    });
    Aib aib;
    aib.init(2*n);
    for(auto &c:a)
    {
        c.rezl=aib.query(c.r);
        aib.update(c.r,c.r);
    }


    std::set<std::pair<int,int>>mpp;
    for(auto &c:a)
    {
        auto it=mpp.lower_bound({c.l,-1});
        std::vector<std::pair<int,int>>aux;
        while(it!=mpp.end() && it->first<=c.r)
        {
            aux.push_back(*it);
            //std::cout<<std::min(c.index,it->second)<<' '<<std::max(c.index,it->second)<<'\n';
            adj[c.index].push_back(it->second);
            adj[it->second].push_back(c.index);
            it++;
        }

        for(auto &v:aux)
        {
            mpp.erase(v);
        }
        mpp.insert({c.r , c.index});
    }
    mpp.clear();

    std::sort(all(a) , [&](interval x,interval y){
       return x.r>y.r;
    });
    aib.init(2*n);
    for(auto &c:a)
    {
        c.rezr=2*n-aib.query(2*n-c.l+1)+1;
        aib.update(2*n-c.l+1 , 2*n-c.l+1);
    }

    for(auto &c:a)
    {
        auto it=mpp.lower_bound({-c.r,-1});
        std::vector<std::pair<int,int>>aux;
        while(it!=mpp.end() && -it->first>=c.l)
        {
            aux.push_back(*it);
            adj[c.index].push_back(it->second);
            adj[it->second].push_back(c.index);
            it++;
        }

        for(auto &v:aux)
        {
            mpp.erase(v);
        }
        mpp.insert({-c.l , c.index});
    }
    mpp.clear();

    for(auto &c:a)
    {
        rez*=(c.rezl<=c.rezr);
    }
    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;
}

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