Submission #672163

#	Time	Username	Problem	Language	Result	Execution time	Memory
672163		urosk	Port Facility (JOI17_port_facility)	C++14	78 / 100	6067 ms	317372 KiB

port_facility

#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include "bits/stdc++.h"
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll int
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}

#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;
#define maxn 2000015
#define mod 1000000007
ll n;
pll a[maxn];
pll t[4*maxn],t2[4*maxn],t3[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));
}
void upd2(ll v,ll tl,ll tr,ll i,pll p){
    if(tl==tr){t2[v] = p;return;}
    ll mid = (tl+tr)/2;
    if(i<=mid) upd2(2*v,tl,mid,i,p);
    else upd2(2*v+1,mid+1,tr,i,p);
    t2[v] = min(t2[2*v],t2[2*v+1]);
}
pll get2(ll v,ll tl,ll tr,ll l,ll r){
    if(l>r) return {llinf,llinf};
    if(tl==l&&tr==r) return t2[v];
    ll mid = (tl+tr)/2;
    return min(get2(2*v,tl,mid,l,min(mid,r)),get2(2*v+1,mid+1,tr,max(mid+1,l),r));
}
void upd3(ll v,ll tl,ll tr,ll i,pll p){
    if(tl==tr){t3[v] = p;return;}
    ll mid = (tl+tr)/2;
    if(i<=mid) upd3(2*v,tl,mid,i,p);
    else upd3(2*v+1,mid+1,tr,i,p);
    t3[v] = max(t3[2*v],t3[2*v+1]);
}
pll get3(ll v,ll tl,ll tr,ll l,ll r){
    if(l>r) return {0,0};
    if(tl==l&&tr==r) return t3[v];
    ll mid = (tl+tr)/2;
    return max(get3(2*v,tl,mid,l,min(mid,r)),get3(2*v+1,mid+1,tr,max(mid+1,l),r));
}
bool vis[maxn];
map<ll,ll> mp;
set<ll> s;
ll it = 0;
ll dept[maxn];
vector<ll> g[maxn];
int main()
{
    daj_mi_malo_vremena;
    cin >> n;
    for(ll i = 1;i<=n;i++) cin >> a[i].fi >> a[i].sc;
    for(ll i = 1;i<=n;i++) s.insert(a[i].fi),s.insert(a[i].sc);
    for(ll x : s) mp[x] = ++it;
    for(ll i = 1;i<=n;i++) a[i].fi = mp[a[i].fi];
    for(ll i = 1;i<=n;i++) a[i].sc = mp[a[i].sc];
    sort(a+1,a+1+n);
    //here;
    //for(ll i = 1;i<=n;i++) cerr<<a[i].fi<< " "<<a[i].sc<<endl;
    for(ll i = 1;i<=n;i++) upd(1,1,2*n,a[i].fi,{a[i].sc,i});
    for(ll i = 1;i<=2*n;i++) upd2(1,1,2*n,i,{llinf,llinf});
    for(ll i = 1;i<=n;i++) upd2(1,1,2*n,a[i].sc,{a[i].fi,i});
    queue<ll> q;
    vector<ll> v,w;
    for(ll i = 1;i<=n;i++){
        if(vis[i]) continue;
        q.push(i);
        upd(1,1,2*n,a[i].fi,{0,0});
        upd2(1,1,2*n,a[i].sc,{llinf,llinf});
        w.clear();
        while(sz(q)){
            ll j = q.front();
            w.pb(j);
            q.pop();
            v.clear();
            vis[j] = 1;
            ll l = a[j].fi,r = a[j].sc;
            while(1){
                pll p = get(1,1,2*n,l,r);
                if(p.fi<=r) break;
                ll x = p.sc;
                dept[x] = dept[j]+1;
                q.push(x);
                upd(1,1,2*n,a[x].fi,{0,0});
                upd2(1,1,2*n,a[x].sc,{llinf,llinf});
            }
            while(1){
                pll p = get2(1,1,2*n,l,r);
                if(p.fi>=l) break;
                ll x = p.sc;
                q.push(x);
                dept[x] = dept[j]+1;
                upd(1,1,2*n,a[x].fi,{0,0});
                upd2(1,1,2*n,a[x].sc,{llinf,llinf});
            }
            //ceri(v,0,sz(v)-1);
        }
        ll mxdub = 0;
        for(ll x : w) mxdub = max(mxdub,dept[x]);
        for(ll x : w) g[dept[x]].pb(x);
        for(ll dub = 0;dub<=mxdub;dub++){
            v.clear();
            for(ll x : g[dub]) v.pb(x);
            for(ll x : v) upd3(1,1,2*n,a[x].fi,{a[x].sc,x});
            for(ll x : v){
                ll l = a[x].fi,r = a[x].sc;
                if(get3(1,1,2*n,l,r).fi>r){
                    cout<<0<<endl;
                    return 0;
                }
            }
            for(ll x : v) upd3(1,1,2*n,a[x].fi,{0,0});
        }
        for(ll dub = 0;dub<=mxdub;dub++) g[dub].clear();
        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: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 56 / 56
• Subtask 4: 0 / 22