Submission #1177576

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

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

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


    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));
    //din stanga in dreapta si invers
    Aib aib;
    aib.init(2*n);
    std::vector<int>l(n);
    for(int i=0;i<n;i++)
    {
        auto& c=a[i];
        l[i]=aib.query(c.second);
        //std::cout<<l[i]<<' ';
        aib.update(c.second,c.second);
    }

    std::sort(all(a) , [&](std::pair<int,int>x,std::pair<int,int>y){
       return x.second<y.second;
    });
    ///std::cout<<'\n';
    std::vector<int>r(n);
    aib.init(2*n);
    for(int i=n-1;i>=0;i--)
    {
        auto& c=a[i];
        r[i]=2*n-aib.query(2*n-c.first+1)+1;
        ///std::cout<<r[i]<<' ';
        aib.update(2*n-c.first+1 , 2*n-c.first+1);
    }
    ///std::cout<<'\n';

    for(int i=0;i<n;i++)
    {
        rez*=(l[i]<=r[i]);
    }
    std::cout<<rez<<'\n';

    return 0;
}
/*
1 4
2 10
3 5
6 9
7 8
*/

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