Submission #671560

#	Time	Username	Problem	Language	Result	Execution time	Memory
671560		urosk	Port Facility (JOI17_port_facility)	C++14	0 / 100	0 ms	212 KiB

port_facility

#include <bits/stdc++.h>
#define here cerr<<"========================================\n"
#define ll long long
#define sz(a) (ll)(a.size())
#define pb push_back
#define popb pop_back
#define pll pair<ll,ll>
#define fi first
#define sc second
#define endl '\n'
using namespace std;
#define maxn 1000000
#define mod 1000000007
ll n;
pll a[maxn];
pll t[4*maxn];
ll ans = 1;
void upd(ll v,ll tl,ll tr,ll i,pll p){
    if(tl==tr){t[v] = p;return;}
    ll mid = (tl+tr)/2;
    if(i<=mid) upd(2*v,tl,mid,i,p);
    else upd(2*v+1,mid+1,tr,i,p);
    t[v] = max(t[2*v],t[2*v+1]);
}
pll get(ll v,ll tl,ll tr,ll l,ll r){
    if(l>r) return {0,0};
    if(tl==l&&tr==r) return t[v];
    ll mid = (tl+tr)/2;
    return max(get(2*v,tl,mid,l,min(mid,r)),get(2*v+1,mid+1,tr,max(mid+1,l),r));
}
ll dsu[maxn];
ll root(ll x){
    while(x!=dsu[x]){
        dsu[x] = dsu[dsu[x]];
        x = dsu[x];
    }
    return x;
}
void upd(ll x,ll y){
    x = root(x); y = root(y);
    if(x==y) ans = 0;
    dsu[x] = y;
}
bool con(ll x,ll y){
    return root(x)==root(y);
}
int main()
{
    cin >> n;
    for(ll i = 1;i<=n;i++) cin >> a[i].fi >> a[i].sc;
    for(ll i = 1;i<=n;i++) upd(1,1,2*n,a[i].fi,{a[i].sc,i});
    iota(dsu+1,dsu+1+n,1);
    vector<ll> v;
    for(ll i = 1;i<=n;i++){
        ll l = a[i].fi,r = a[i].sc;
        v.clear();
        while(1){
            pll p = get(1,1,2*n,l+1,r-1);
            ll x = p.sc;
            ll R = p.fi;
            if(R<r) break;
            //cerr<<"a: "<<i<< " "<<x<<endl;
            v.pb(x);
            upd(i,x);
            upd(1,1,2*n,a[x].fi,{0,0});
        }
        for(ll x : v) upd(1,1,2*n,a[x].fi,{a[x].sc,x});
    }
    set<ll> s;
    for(ll i = 1;i<=n;i++) s.insert(root(i));
    ll x = sz(s);
    while(x--){
        ans*=2;
        if(ans>=mod) ans%=mod;
    }
    cout<<ans<<endl;
    return 0;
}
/*
4
1 3
2 5
4 8
6 7
ans: 4

3
1 4
2 5
3 6
ans: 0

5
1 4
2 10
6 9
7 8
3 5
ans: 8

8
1 15
2 5
3 8
4 6
14 16
7 9
10 13
11 12
ans: 16

*/

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