Submission #1101828

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101828		irmuun	Port Facility (JOI17_port_facility)	C++17	100 / 100	3316 ms	442744 KiB

port_facility

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

const ll mod=1e9+7;

struct segtree_max{
    vector<pair<ll,ll>>d;
    segtree_max(ll n){
        d.resize(4*n);
        build(1,1,n);
    }
    void build(ll node,ll l,ll r){
        if(l==r){
            d[node]={-1e18,-1e18};
            return;
        }
        ll mid=(l+r)/2;
        build(node*2,l,mid);
        build(node*2+1,mid+1,r);
        d[node]=max(d[node*2],d[node*2+1]);
    }
    pair<ll,ll>query(ll node,ll l,ll r,ll L,ll R){
        if(l > R || r < L || L > R){
            return {-1e18,-1e18};
        }
        if(L <= l && r <= R){
            return d[node];
        }
        ll mid=(l+r)/2;
        return max(query(node*2,l,mid,L,R),query(node*2+1,mid+1,r,L,R));
    }
    void update(ll node,ll l,ll r,ll L,ll R,ll i){
        if(l>L || r<L)return;
        if(l==r){
            d[node]={R,i};
            return;
        }
        ll mid=(l+r)/2;
        update(node*2,l,mid,L,R,i);
        update(node*2+1,mid+1,r,L,R,i);
        d[node]=max(d[node*2],d[node*2+1]);
    }
};

struct segtree_min{
    vector<pair<ll,ll>>d;
    segtree_min(ll n){
        d.resize(4*n);
        build(1,1,n);
    }
    void build(ll node,ll l,ll r){
        if(l==r){
            d[node]={1e18,1e18};
            return;
        }
        ll mid=(l+r)/2;
        build(node*2,l,mid);
        build(node*2+1,mid+1,r);
        d[node]=min(d[node*2],d[node*2+1]);
    }
    pair<ll,ll>query(ll node,ll l,ll r,ll L,ll R){
        if(l > R || r < L || L > R){
            return {1e18,1e18};
        }
        if(L <= l && r <= R){
            return d[node];
        }
        ll mid=(l+r)/2;
        return min(query(node*2,l,mid,L,R),query(node*2+1,mid+1,r,L,R));
    }
    void update(ll node,ll l,ll r,ll L,ll R,ll i){
        if(l>L || r<L)return;
        if(l==r){
            d[node]={R,i};
            return;
        }
        ll mid=(l+r)/2;
        update(node*2,l,mid,L,R,i);
        update(node*2+1,mid+1,r,L,R,i);
        d[node]=min(d[node*2],d[node*2+1]);
    }
};

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n;
    cin>>n;
    vector<ll>a(n+1),b(n+1);
    for(ll i=1;i<=n;i++){
        cin>>a[i]>>b[i];
    }
    segtree_min smn(2*n);
    segtree_max smx(2*n);
    for(ll i=1;i<=n;i++){
        smn.update(1,1,2*n,a[i],b[i],i);
        smx.update(1,1,2*n,a[i],b[i],i);
        smn.update(1,1,2*n,b[i],a[i],i);
        smx.update(1,1,2*n,b[i],a[i],i);
    }
    vector<vector<ll>>g(n+1);
    for(ll i=1;i<=n;i++){
        auto mn=smn.query(1,1,2*n,a[i]+1,b[i]-1),mx=smx.query(1,1,2*n,a[i]+1,b[i]-1);
        if(mn.ff<a[i]) g[mn.ss].pb(i), g[i].pb(mn.ss);
        if(mx.ff>b[i]) g[mx.ss].pb(i), g[i].pb(mx.ss);
    }
    vector<ll>col(n+1,-1);
    ll ans=1;
    function <void(ll)> dfs=[&](ll x){
        for(ll y:g[x]){
            if(col[y]==-1){
                col[y]=1-col[x];
                dfs(y);
            }
            if(col[x]==col[y]){
                ans=0;
            }
        }
    };
    for(ll i=1;i<=n;i++){
        if(col[i]==-1){
            ans=ans*2%mod;
            col[i]=0;
            dfs(i);
        }
    }
    cout<<ans;
}

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