Submission #800186

#	Time	Username	Problem	Language	Result	Execution time	Memory
800186		vjudge1	Port Facility (JOI17_port_facility)	C++14	78 / 100	6064 ms	248928 KiB

port_facility

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std ;
const ll N = (1 << 21), mod = 1e9 + 7 ;
bool flag, us[N + 1] ;
ll n, cnt, color[N + 1], a[N + 1], b[N + 1] ;
pair<ll, ll> mn[2 * N + 1], mx[2 * N + 1] ;
ll 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(int l, int r, int v)
{
    if(l == r)
    {
        mx[v] = {-1e9, l} ;
        mn[v] = {1e9, l} ;
        return ;
    }
    int mid = (l + r) >> 1 ;
    build(l, mid, v * 2) ;
    build(mid + 1, r, v * 2 + 1) ;
    mx[v] = max(mx[v * 2], mx[v * 2 + 1]) ;
    mn[v] = min(mn[v * 2], mn[v * 2 + 1]) ;
}
void update_min(int l, int r, int pos, pair<int, int> p, int v)
{
    if(l > pos || r < pos)
        return ;
    if(l == r)
    {
        mn[v] = p ;
        return ;
    }
    int mid = (l + r) >> 1 ;
    update_min(l, mid, pos, p, v * 2) ;
    update_min(mid + 1, r, pos, p, v * 2 + 1) ;
    mn[v] = min(mn[v * 2], mn[v * 2 + 1]) ;
}
void update_max(int l, int r, int pos, pair<int, int> p, int v)
{
    if(l > pos || r < pos)
        return ;
    if(l == r)
    {
        mx[v] = p ;
        return ;
    }
    int mid = (l + r) >> 1 ;
    update_max(l, mid, pos, p, v * 2) ;
    update_max(mid + 1, r, pos, p, v * 2 + 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 {-1e9, 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 {1e9, 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(1, N, a[city], {-1e9, city}, 1) ;
    update_min(1, N, b[city], {1e9, city}, 1) ;
    while(abu)
    {
        abu ^= 1 ;
        pair<int, int> lf = get_min(1, N, a[city], b[city], 1), rg = get_max(1, N, 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(1, N, 1) ;
    for(ll i = 1 ; i <= n ; i++)
    {
        cin >> a[i] >> b[i] ;
        update_min(1, N, b[i], {a[i], i}, 1) ;
        update_max(1, N, a[i], {b[i], i}, 1) ;
    }
    for(int i = 1 ; i <= n ; i++)
    {
        if(us[i])
            continue ;
        cnt++ ;
        dfs(i) ;
    }
    for(int j = 0 ; j < 2 ; j++)
    {
        build(1, N, 1) ;
        for(int i = 1 ; i <= n ; i++)
            if(color[i] == j)
            {
                update_min(1, N, b[i], {a[i], i}, 1) ;
                update_max(1, N, a[i], {b[i], i}, 1) ;
            }
        for(int i = 1 ; i <= n ; i++)
        {
            if(color[i] != j)
                continue ;
            pair<int, int> lf = get_min(1, N, a[i], b[i], 1), rg = get_max(1, N, 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