Submission #800227

#	Time	Username	Problem	Language	Result	Execution time	Memory
800227		vjudge1	Port Facility (JOI17_port_facility)	C++14	78 / 100	6015 ms	184224 KiB

port_facility

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#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 flag, us[N + 1], color[N + 1] ;
int n, cnt, a[N + 1], b[N + 1] ;
pair<int, int> mn[2 * N1 + 1], mx[2 * N1 + 1] ;
int binpow(ll num, ll pw)
{
    ll res = 1 ;
    while(pw)
        if(pw & 1)
        {
            res *= num ;
            pw ^= 1 ;
            res %= mod ;
        }
        else
        {
            num *= num ;
            pw >>= 1 ;
            num %= mod ;
        }
    return res ;
}
void build()
{
    for(int i = 1 ; i <= 2 * N1 ; i++)
    {
        mx[i] = {-N1 * 4, 0} ;
        mn[i] = {N1 * 4, 0} ;
    }
}
void update_min(int v, pair<int, int> p)
{
    mn[v] = p ;
    while(v > 1)
    {
        v >>= 1 ;
        mn[v] = min(mn[v * 2], mn[v * 2 + 1]) ;
    }
}
void update_max(int v, pair<int, int> p)
{
    mx[v] = p ;
    while(v > 1)
    {
        v >>= 1 ;
        mx[v] = max(mx[v * 2], mx[v * 2 + 1]) ;
    }
}
pair<int, int> get_max(int l, int r, int l1, int r1, int v)
{
    if(l > r1 || r < l1)
        return {-4 * N1, 0} ;
    if(l1 <= l && r <= r1)
        return mx[v] ;
    int mid = (l + r) >> 1 ;
    pair<int, int> p1 = get_max(l, mid, l1, r1, v * 2), p2 = get_max(mid + 1, r, l1, r1, v * 2 + 1) ;
    return max(p1, p2) ;
}
pair<int, int> get_min(int l, int r, int l1, int r1, int v)
{
    if(l > r1 || r < l1)
        return {4 * N1, 0} ;
    if(l1 <= l && r <= r1)
        return mn[v] ;
    int mid = (l + r) >> 1 ;
    pair<int, int> p1 = get_min(l, mid, l1, r1, v * 2), p2 = get_min(mid + 1, r, l1, r1, v * 2 + 1) ;
    return min(p1, p2) ;
}
void dfs(int city)
{
    bool abu = 1 ;
    us[city] = 1 ;
    update_max(a[city] + N1 - 1, {-4 * N1, city}) ;
    update_min(b[city] + N1 - 1, {4 * N1, city}) ;
    while(abu)
    {
        abu ^= 1 ;
        pair<int, int> lf = get_min(1, N1, a[city], b[city], 1), rg = get_max(1, N1, a[city], b[city], 1) ;
        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 ;
        }
    }
}
signed 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] - 1 + N1, {a[i], i}) ;
        update_max(a[i] - 1 + N1, {b[i], i}) ;
    }
    for(int i = 1 ; i <= n ; i++)
    {
        if(us[i])
            continue ;
        cnt++ ;
        dfs(i) ;
    }
    for(int j = 0 ; j < 2 ; j++)
    {
        build() ;
        for(int i = 1 ; i <= n ; i++)
            if(color[i] == j)
            {
                update_min(b[i] - 1 + N1, {a[i], i}) ;
                update_max(a[i] - 1 + N1, {b[i], i}) ;
            }
        for(int i = 1 ; i <= n ; i++)
        {
            if(color[i] ^ j)
                continue ;
            pair<int, int> lf = get_min(1, N1, a[i], b[i], 1), rg = get_max(1, N1, a[i], b[i], 1) ;
            if(lf.fi < a[i] || rg.fi > b[i])
                flag = 1 ;
        }
    }
    if(flag)
        cout << "0\n" ;
    else
        cout << binpow(2, cnt) ;
    return 0 ;
}

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