Submission #800348

#	Time	Username	Problem	Language	Result	Execution time	Memory
800348		vjudge1	Port Facility (JOI17_port_facility)	C++14	100 / 100	3138 ms	168620 KiB

port_facility

#include<iostream>
#define ll long long
#define fi first
#define se second
using namespace std ;
const int N = (1 << 20), N1 = (1 << 21), mod = 1e9 + 7 ;
bool us[N + 1], color[N + 1] ;
int n, ans = 1, a[N + 1], b[N + 1] ;
pair<int, int> mn[2 * N1 + 1], mx[2 * N1 + 1] ;
void build()
{
    for(int i = 1 ; i <= 2 * N1 ; i++)
    {
        mx[i] = {-N1 * 4, 0} ;
        mn[i] = {N1 * 4, 0} ;
    }
}
void update_min(int index, pair<int, int> p)
{
	mn[index + N1] = p;
	for (index += N1; index > 1; index /= 2)
		mn[index / 2] = min(mn[index], mn[index ^ 1]) ;
}
void update_max(int index, pair<int, int> p)
{
	mx[index + N1] = p;
	for (index += N1; index > 1; index /= 2)
		mx[index / 2] = max(mx[index], mx[index ^ 1]) ;
}
pair<int, int> get_min(int l1, int r1)
{
    l1 += N1 ;
    r1 += N1 ;
    pair<int, int> mn1 = {1e9, 0} ;
    while(l1 <= r1)
    {
//        cout<<l1<<' '<<r1<<'\n' ;
        if(l1 % 2)mn1 = min(mn[l1++], mn1) ;
        if(r1 % 2 == 0)mn1 = min(mn[r1--], mn1) ;
        l1 >>= 1 ;
        r1 >>= 1 ;
    }
    return mn1 ;
}
pair<int, int> get_max(int l1, int r1)
{
    l1 += N1 ;
    r1 += N1 ;
    pair<int, int> mx1 = {-1e9, 0} ;
    while(l1 <= r1)
    {
//        cout<<l1<<' '<<r1<<'\n' ;
        if(l1 % 2)mx1 = max(mx[l1++], mx1) ;
        if(r1 % 2 == 0)mx1 = max(mx[r1--], mx1) ;
        l1 >>= 1 ;
        r1 >>= 1 ;
    }
    return mx1 ;
}
void dfs(int city)
{
//    cout<<city<<' ' ;
    bool abu = 1 ;
    us[city] = 1 ;
    update_max(a[city], {-4 * N1, city}) ;
    update_min(b[city], {4 * N1, city}) ;
    while(abu)
    {
        abu ^= 1 ;
        pair<int, int> lf = get_min(a[city], b[city]), rg = get_max(a[city], b[city]) ;
//        cout << a[city]<<' '<<b[city] << ' ' << lf.fi<<' '<<rg.fi<<'\n' ;
        if(lf.fi < a[city])
        {
            color[lf.se] = (1 ^ color[city]) ;
            dfs(lf.se) ;
            abu = 1 ;
        }
        if(rg.fi > b[city])
        {
            color[rg.se] = (1 ^ color[city]) ;
            dfs(rg.se) ;
            abu = 1 ;
        }
    }
}
int main()
{
    ios_base::sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cout.tie( 0 ) ;
    cin >> n ;
    build() ;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> a[i] >> b[i] ;
        update_min(b[i], {a[i], i}) ;
        update_max(a[i], {b[i], i}) ;
    }
    for(int i = 1 ; i <= n ; i++)
    {
        if(us[i])
            continue ;
        ans <<= 1 ;
        ans %= mod ;
        dfs(i) ;
//        cout<<"\n_________________\n" ;
    }
//    for(int i = 1 ; i <= n ; i++)
//        cout<<color[i]<<' ' ;
//    cout << '\n' ;
    for(int j = 0 ; j < 2 ; j++)
    {
        build() ;
        for(int i = 1 ; i <= n ; i++)
            if(color[i] == j)
            {
                update_min(b[i], {a[i], i}) ;
                update_max(a[i], {b[i], i}) ;
            }
        for(int i = 1 ; i <= n ; i++)
        {
            if(color[i] ^ j)
                continue ;
            pair<int, int> lf = get_min(a[i], b[i]), rg = get_max(a[i], b[i]) ;
            if(lf.fi < a[i] || rg.fi > b[i])
            {
//                cout<<a[i]<<' '<<b[i]<<' '<<lf.fi << ' ' << lf.se<<' '<<rg.fi<<' '<<rg.se<<'\n' ;
                cout << "0\n" ;
                return 0 ;
            }
        }
    }
    cout << ans ;
    return 0 ;
}

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