Submission #363251

#	Time	Username	Problem	Language	Result	Execution time	Memory
363251		denkendoemeer	Port Facility (JOI17_port_facility)	C++14	100 / 100	1656 ms	93548 KiB

port_facility

#include<bits/stdc++.h>
#define ll long long
const int inf=1e9;
#define mod 1000000007
using namespace std;
map<int,int>mp;
pair<int,int>v[1000005];
int t[2000005];
int findt(int nod)
{
    if (nod==t[nod])
        return nod;
    return t[nod]=findt(t[nod]);
}
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int n,i;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d%d",&v[i].first,&v[i].second);
    }
    sort(v+1,v+n+1);
    for(i=1;i<=2*n;i++)
        t[i]=i;
    for(i=1;i<=n;i++){
        auto a=mp.lower_bound(v[i].first);
        auto b=mp.upper_bound(v[i].second);
        if (b!=mp.begin()){
            for(;a!=b;a++){
                t[findt(i)]=findt(a->second+n);
                t[findt(i+n)]=findt(a->second);
                if (findt(a->second)==findt(prev(b)->second))
                    break;
            }
        }
        mp[v[i].second]=i;
    }
    for(i=1;i<=n;i++)
        if (findt(i)==findt(i+n)){
            printf("0\n");
            return 0;
        }
    ll ans=1;
    for(i=1;i<=n;i++)
        if (findt(i)==i)
            ans=ans*2%mod;
    printf("%lld\n",ans);
return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   20 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
port_facility.cpp:22:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   22 |         scanf("%d%d",&v[i].first,&v[i].second);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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