Submission #21421

#	Time	Username	Problem	Language	Result	Execution time	Memory
21421		sbansalcs	Port Facility (JOI17_port_facility)	C++14	22 / 100	3500 ms	22612 KiB

port_facility

#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
const int N = 1e6+5,mod=1e9+7;
pair<int, int> arr[N];
int parent[N];
int up[N];
int height[N];
multiset<pair<int, int>> st;
int tot=0;
int find_p(int x)  {
    if(x==parent[x])    return x;
    int p=find_p(parent[x]);
    up[x]=(up[x]+up[parent[x]])%2;
    parent[x]=p;
    return parent[x];
}
int val_2(int x)    {
    x%=2;x+=2;x%=2;
    return x;
}
bool union_set(int a, int b, int t)    {
    int u=find_p(a);
    int v=find_p(b);
    if(u==v)    return val_2(up[a]+up[b]-t)==0;
    int x=val_2(t-up[a]-up[b]);
    tot++;
    if(height[u]<height[v]) swap(u, v);
    parent[v]=u;
    height[u]=max(height[u],height[v]+1);
    up[v]=x;
    return true;
}
int main() {
    int n;scanf("%d",&n);
    for (int i=1; i<=n; i++) {
        parent[i]=i;
        height[i]=0;
        up[i]=0;
        scanf("%d %d",&arr[i].first,&arr[i].second);
    }
    sort(arr+1,arr+1+n);
    for (int i=1; i<=n; i++) {
//        cout<<"hoo: "<<i<<endl;
        while (!st.empty() && (*st.begin()).first<arr[i].first) {
            st.erase(st.begin());
        }
        for(auto c:st)  {
            if(c.first<arr[i].second)   {
                if(!union_set(c.second, i, 1))  {
                    cout<<0;return 0;
                }
            }
        }
        st.insert({arr[i].second,i});
    }
    ll ans=1;
    for (int i=n-tot; i>=1; i--) {
        ans*=2;ans%=mod;
    }
    cout<<ans<<endl;
    return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:37:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int n;scanf("%d",&n);
                         ^
port_facility.cpp:42:52: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&arr[i].first,&arr[i].second);
                                                    ^

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