Submission #1101384

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101384		irmuun	Port Facility (JOI17_port_facility)	C++17	0 / 100	1 ms	336 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{
    ll n;
    vector<ll>d;
    segtree(ll n){
        d.resize(4*n);
        build(1,1,n);
    }
    void build(ll node,ll l,ll r){
        if(l==r){
            d[node]=0;
            return;
        }
        ll mid=(l+r)/2;
        build(node*2,l,mid);
        build(node*2+1,mid+1,r);
        d[node]=d[node*2]+d[node*2+1];
    }
    ll query(ll node,ll l,ll r,ll L,ll R){
        if(l > R || r < L || L > R){
            return 0ll;
        }
        if(L <= l && r <= R){
            return d[node];
        }
        ll mid=(l+r)/2;
        return 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 k,ll val){
        if(l>k || r<k)return;
        if(l==r){
            d[node]=val;
            return;
        }
        ll mid=(l+r)/2;
        update(node*2,l,mid,k,val);
        update(node*2+1,mid+1,r,k,val);
        d[node]=d[node*2]+d[node*2+1];
    }
};

struct dsu{
    vector<ll>p,sz;
    dsu(ll n){
        p.resize(n+1);
        iota(all(p),0);
        sz.resize(n+1);
        fill(all(sz),1);
    }
    ll find(ll x){
        if(p[x]==x){
            return x;
        }
        return p[x]=find(p[x]);
    }
    bool same(ll x,ll y){
        x=find(x);
        y=find(y);
        if(x==y){
            return true;
        }
        else{
            return false;
        }
    }
    void merge(ll x,ll y){
        x=find(x);
        y=find(y);
        if(x!=y){
            if(sz[x]<sz[y]){
                swap(x,y);
            }
            sz[x]+=sz[y];
            p[y]=x;
        }
    }
};

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);
    vector<ll>event(2*n+1);
    vector<array<ll,3>>d;
    for(ll i=1;i<=n;i++){
        cin>>a[i]>>b[i];
        d.pb({a[i],b[i],i});
        event[a[i]]=i;
        event[b[i]]=i;
    }
    dsu ds(n);
    sort(all(d));
    for(ll i=1;i<n;i++){
        if(d[i][0]<d[i-1][1]&&d[i-1][1]<d[i][1]){
            ds.merge(d[i-1][2],d[i][2]);
        }
    }
    vector<vector<ll>>v(n+1);
    for(ll i=1;i<=n;i++){
        ll j=ds.find(i);
        v[j].pb(i);
    }
    vector<pair<ll,ll>>seg(n+1);
    for(ll i=1;i<=n;i++){
        if(v[i].empty()) continue;
        ll l=2*n,r=1;
        for(ll j:v[i]){
            l=min(l,a[j]);
            r=max(r,b[j]);
        }
        seg[i].ff=l;
        seg[i].ss=r;
    }
    vector<ll>l(n+1),r(n+1);
    for(ll i=1;i<=n;i++){
        ll j=ds.find(i);
        l[i]=seg[j].ff;
        r[i]=seg[j].ss;
    }
    vector<ll>col(n+1,-1);
    segtree sg0(2*n),sg1(2*n);
    ll ans=1;
    for(ll i=1;i<=2*n;i++){
        ll j=event[i];
        if(a[j]==i){
            vector<ll>cnt(2,0);
            cnt[0]=sg0.query(1,1,2*n,l[j],r[j]);
            cnt[1]=sg1.query(1,1,2*n,l[j],r[j]);
            if(cnt[0]+cnt[1]==0){
                ans=ans*2%mod;
                col[j]=0;
            }
            else if(cnt[0]>0&&cnt[1]>0){
                cout<<0;
                return 0;
            }
            else if(cnt[0]==0){
                col[j]=0;
            }
            else{
                col[j]=1;
            }
            if(col[j]==0){
                sg0.update(1,1,2*n,b[j],1);
                sg0.update(1,1,2*n,a[j],1);
            }
            else{
                sg1.update(1,1,2*n,b[j],1);
                sg1.update(1,1,2*n,a[j],1);
            }
        }
        else{
            if(col[j]==0){
                sg0.update(1,1,2*n,b[j],0);
                sg0.update(1,1,2*n,a[j],0);
            }
            else{
                sg1.update(1,1,2*n,b[j],0);
                sg1.update(1,1,2*n,a[j],0);
            }
        }
    }
    cout<<ans;
}

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