Submission #71929

#	Time	Username	Problem	Language	Result	Execution time	Memory
71929		Bruteforceman	Port Facility (JOI17_port_facility)	C++11	100 / 100	4891 ms	651860 KiB

port_facility

    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    typedef pair<int, int> pii;
    const int MX=1000010, inf=2e9, MOD=1e9+7;
     
    int n, S[MX], E[MX];
     
    inline pii _min(const pii &a, const pii &b){ return a.first<b.first ? a : b; }
    inline pii _max(const pii &a, const pii &b){ return a.first>b.first ? a : b; }
    const pii pninf=pii(inf,-1), pxinf=pii(0, -1);
     
    pii ntree[1<<22], xtree[1<<22];
     
    void init(){
        for(int i=1; i<(1<<22); i++)
            ntree[i]=pninf, xtree[i]=pxinf;
    }
     
    pii mn(int v, int s, int e, int l, int r){
        if(l<=s && e<=r) return ntree[v];
        int m=(s+e)/2;
        if(r<=m) return mn(v*2,s,(s+e)/2,l,r);
        if(m+1<=l) return mn(v*2+1,(s+e)/2+1,e,l,r);
        return _min(mn(v*2,s,(s+e)/2,l,r), mn(v*2+1,(s+e)/2+1,e,l,r));
    }
    pii mx(int v, int s, int e, int l, int r){
        if(l<=s && e<=r) return xtree[v];
        int m=(s+e)/2;
        if(r<=m) return mx(v*2,s,(s+e)/2,l,r);
        if(m+1<=l) return mx(v*2+1,(s+e)/2+1,e,l,r);
        return _max(mx(v*2,s,(s+e)/2,l,r), mx(v*2+1,(s+e)/2+1,e,l,r));
    }
    pii mn(int l, int r){
        return mn(1,1,2*n,l,r);
    }
    pii mx(int l, int r){
        return mx(1,1,2*n,l,r);
    }
     
    void nupt(int v, int s, int e, int pos, const pii &val){
        if(s==e){
            ntree[v]=val;
            return;
        }
        int m=(s+e)/2;
        if(pos<=m) nupt(v*2,s,(s+e)/2,pos,val);
        else nupt(v*2+1,(s+e)/2+1,e,pos,val);
        ntree[v]=_min(ntree[v*2], ntree[v*2+1]);
    }
    void xupt(int v, int s, int e, int pos, const pii &val){
        if(s==e){
            xtree[v]=val;
            return;
        }
        int m=(s+e)/2;
        if(pos<=m) xupt(v*2,s,(s+e)/2,pos,val);
        else xupt(v*2+1,(s+e)/2+1,e,pos,val);
        xtree[v]=_max(xtree[v*2], xtree[v*2+1]);
    }
     
    void nupt(int pos, const pii &val){
        nupt(1,1,2*n,pos,val);
    }
     
    void xupt(int pos, const pii &val){
        xupt(1,1,2*n,pos,val);
    }
     
    bool vis[MX];
    int col[MX];
     
    void dfs(int v, int c=0){
        vis[v]=true; col[v]=c;
        nupt(E[v], pninf);
        xupt(S[v], pxinf);
        while(true){
            pii q=mx(S[v], E[v]);
            if(q.first<E[v]) break;
            else dfs(q.second, 1-c);
        }
        while(true){
            pii q=mn(S[v], E[v]);
            if(S[v]<q.first) break;
            else dfs(q.second, 1-c);
        }
    }
     
    int H[2*MX], cnt[2*MX];
    bool valid(){
        for(int i=1; i<=n; i++){
            assert(vis[i]);
            if(col[i]!=0) continue;
            cnt[S[i]]++, cnt[E[i]+1]--;
        }
        for(int i=1, now=0; i<=2*n+1; i++){
            now+=cnt[i]; cnt[i]=0;
            H[i]=now;
        }
        for(int i=1; i<=n; i++){
            if(col[i]!=0) continue;
            if(H[S[i]]!=H[E[i]]) return false;
        }
        for(int i=1; i<=n; i++){
            if(col[i]!=1) continue;
            cnt[S[i]]++, cnt[E[i]+1]--;
        }
        for(int i=1, now=0; i<=2*n+1; i++){
            now+=cnt[i]; cnt[i]=0;
            H[i]=now;
        }
        for(int i=1; i<=n; i++){
            if(col[i]!=1) continue;
            if(H[S[i]]!=H[E[i]]) return false;
        }
        return true;
    }
     
    int main(){
        ios::sync_with_stdio(0); cin.tie(0);
        cin>>n;
        init();
        for(int i=1; i<=n; i++){
            cin>>S[i]>>E[i];
            nupt(E[i], pii(S[i], i));
            xupt(S[i], pii(E[i], i));
        }
        int ans=1;
        for(int i=1; i<=n; i++){
            if(!vis[i]) dfs(i), ans=ans*2%MOD;
        }
        cout<<(valid() ? ans : 0);
        return 0;
    }

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