Submission #1178573

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178573		ASN49K	Port Facility (JOI17_port_facility)	C++20	22 / 100	219 ms	55236 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;

namespace solve_normal
{
    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);
        }
    }
    int solve()
    {
        ///auto __file = freopen("input.txt","r",stdin);
        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);
                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.r , c.index});
        }
        mpp.clear();
        ///std::cout<<'\n';

        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;
                }
            }
        }



        ///fclose(__file);

        ///std::cerr<<"wtff";
        return rez;
    }
}

namespace solve_brut
{
    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 solve()
    {
        auto __file = freopen("input.txt","r",stdin);
        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();
        }
        std::vector<std::pair<int,int>>a(n);
        for(auto &c:a)
        {
            std::cin>>c.first>>c.second;
        }
        std::sort(all(a));
//        for(auto &c:a)
//        {
//            std::cout<<c.first<<' '<<c.second<<'\n';
//        }
        ///std::cerr<<n<<'\n';
        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::cerr<<"x0x";
        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;
                }
            }
        }

        fclose(__file);

        return rez;
    }
}


void normal()
{
    ///NU UITA INPUT SUS
    solve_normal::solve();
    exit(0);
}


int range(int l,int r)
{
    return l+rng()%(r-l+1);
}
int main()
{

    //std::cout<<solve_brut::solve();
    std::cout<<solve_normal::solve();//<<' '<<solve_brut::solve()<<'\n';
    return 0;


    while(true)
    {
        std::ofstream fout("input.txt");
        int n=range(5,6);
        std::vector<int>a(2*n);
        std::iota(all(a) , 0);
        std::shuffle(all(a) , rng);

        fout<<n<<'\n';
        for(auto &c:a)
        {
            c/=2;
            assert(c>=0 && c<n);
        }
        std::vector<std::vector<int>>pii(n);
        for(int i=0;i<2*n;i++)
        {
            pii[a[i]].push_back(i+1);
        }
        for(auto &c:pii)
        {
            for(auto &v:c)
            {
                fout<<v<<' ';
            }
            fout<<'\n';
        }
        //std::cin.get();
        fout.close();


        if(solve_normal::solve()!=solve_brut::solve())
        {
            break;
        }
        ///std::cerr<<n<<'\n';
    }
}
/*
6
2 5
3 12
4 7
6 11
1 10
8 9

prima sortare
1 10
2 5
3 12
4 7
6 11
8 9

graful este de fapt
0 2
0 4
1 2
1 3
3 4
*/

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