Submission #60033

#	Time	Username	Problem	Language	Result	Execution time	Memory
60033		Diuven	Port Facility (JOI17_port_facility)	C++11	100 / 100	5542 ms	195016 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