Submission #238757

#	Time	Username	Problem	Language	Result	Execution time	Memory
238757		DodgeBallMan	Port Facility (JOI17_port_facility)	C++14	100 / 100	1492 ms	85460 KiB

port_facility

#include <bits/stdc++.h>

#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 2e6 + 10;

long long mod = 1e9 + 7;
vector<pii> vec;
int par[N], n;
map<int, int> mp;

int findroot( int now ) { return par[now] == now ? now : par[now] = findroot( par[now] ); }

int main()
{
    for( int i = 1 ; i < N ; i++ ) par[i] = i;
    scanf("%d",&n);
    for( int i = 1, x, y ; i <= n ; i++ ) {
        scanf("%d %d",&x,&y);
        vec.emplace_back( x, y );
    }
    sort( vec.begin(), vec.end() );
    for( int i = 0 ; i < n ; i++ ) {
        auto l = mp.lower_bound( vec[i].x ), r = mp.upper_bound( vec[i].y );
        if( r != mp.begin() ) {
            for( ; l != r ; l++ ) {
                par[findroot(i)] = findroot( l->y + n );
                par[findroot(i+n)] = findroot( l->y );
                if( findroot(l->y) == findroot( prev(r)->y )) break;
            }
        }
        mp[vec[i].y] = i;   
    }
    for( int i = 0 ; i < n ; i++ ) if( findroot( i ) == findroot( i+n ) ) return !printf("0\n");
    long long ans = 1;
    for( int i = 0 ; i < n ; i++ ) if( findroot( i ) == i ) ans = ( ans * 2LL ) % mod;
    printf("%lld\n",ans);
    return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
port_facility.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&x,&y);
         ~~~~~^~~~~~~~~~~~~~~

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