Submission #329848

#	Time	Username	Problem	Language	Result	Execution time	Memory
329848		milisav	Port Facility (JOI17_port_facility)	C++14	100 / 100	5458 ms	232940 KiB

port_facility

#include<bits/stdc++.h>
#define maxn 2500000
using namespace std;
struct treap {
    treap *l,*r;
    int val;
    unsigned long long prior;
    treap(int val,unsigned long long prior) {
        this->l=NULL;
        this->r=NULL;
        this->val=val;
        this->prior=prior;
    }
};
unsigned long long seed=122837128964317283;
unsigned long long tot=0;
unsigned long long rng() {
    tot+=seed;
    return tot;
}
inline void split(treap* t,treap* &l,treap* &r,int x) {
    if(t==NULL) {
        l=r=NULL;
    }
    else {
        if(t->val<x) {
            split(t->r,t->r,r,x);
            l=t;
        }
        else {
            split(t->l,l,t->l,x);
            r=t;
        }
    }
}
inline void join(treap* &t,treap* l,treap* r) {
    if(l==NULL) t=r;
    else {
        if(r==NULL) t=l;
        else {
            if(l->prior>r->prior) {
                join(l->r,l->r,r);
                t=l;
            }
            else {
                join(r->l,l,r->l);
                t=r;
            }
        }
    }
}
inline int left(treap* t) {
     if(t->l==NULL) return t->val;
     else return left(t->l);
}
inline int right(treap* t) {
     if(t->r==NULL) return t->val;
     else return right(t->r);
}
void pop_left(treap* &t) {
    if(t->l==NULL) {
        t=t->r;
        return;
    }
    else pop_left(t->l);
}
int n;
int a[maxn];
int b[maxn];
int par[maxn];
int ord[maxn];
vector<int> c[maxn];
int d[maxn];
bool vis[maxn];
void dfs(int u) {
    vis[u]=true;
    for(auto v:c[u]) {
        if(!vis[v]) {
            d[v]=d[u]^1;
            dfs(v);
        }
    }
}
int act_c[4*maxn];
vector<int> cur_c;
treap* tq[maxn];
long long mod=1000000007;
int find_par(int u) {
    if(par[u]==u) return u;
    par[u]=find_par(par[u]);
    return par[u];
}
void print_par() {
    for(int i=1;i<=n;i++) {
        cerr<<"par["<<i<<"]="<<par[i]<<endl;
    }
}
void unite(int u,int v) {
    par[u]=v;
    if(right(tq[u])<left(tq[v])) {
        treap *tmp;
        join(tmp,tq[u],tq[v]);
        tq[v]=tmp;
    }
    else {
        if(right(tq[v])<left(tq[u])) {
            treap *tmp;
            join(tmp,tq[v],tq[u]);
            tq[v]=tmp;
        }
        else {
            assert(left(tq[u])==right(tq[u]) || left(tq[v])==right(tq[v]));
            if(left(tq[u])==right(tq[u])) {
                treap *l,*r,*tmp,*ans;
                split(tq[v],l,r,left(tq[u]));
                join(tmp,l,tq[u]);
                join(ans,tmp,r);
                tq[v]=ans;
            }
            else {
                treap *l,*r,*tmp,*ans;
                split(tq[u],l,r,left(tq[v]));
                join(tmp,l,tq[v]);
                join(ans,tmp,r);
                tq[v]=ans;
            }
        }
    }
}
inline void clear(int id,int l,int r) {
    if(act_c[id]==0) return;
    if(l==r) {
        cur_c.push_back(-ord[l]);
        return;
    }
    act_c[id]=0;
    int m=(l+r)/2;
    clear(id*2+1,l,m);
    clear(id*2+2,m+1,r);
}
inline void active(int id,int l,int r,int x,int y) {
    if(x<=l && r<=y) {
        clear(id,l,r);
        return;
    }
    if(y<l || r<x) return;
    int m=(l+r)/2;
    active(id*2+1,l,m,x,y);
    active(id*2+2,m+1,r,x,y);
    act_c[id]=act_c[id*2+1]+act_c[id*2+2];
}
void update(int id,int l,int r,int p,int v) {
    if(l==r) {
        act_c[id]+=v;
        return;
    }
    int m=(l+r)/2;
    if(p<=m) update(id*2+1,l,m,p,v);
    else update(id*2+2,m+1,r,p,v);
    act_c[id]=act_c[id*2+1]+act_c[id*2+2];
}
stack<int> s[2];
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d %d",&a[i],&b[i]);
    for(int i=1;i<=n;i++) {
        ord[a[i]]=i;
        ord[b[i]]=-i;
        par[i]=i;
        tq[i]=new treap(b[i],rng());
    }
    //cerr<<"ok1"<<endl;
    for(int i=1;i<=2*n;i++) {
        //cerr<<i<<" "<<ord[i]<<endl;
        if(ord[i]>0) {
            int j=ord[i];
            cur_c.clear();
            active(0,1,2*n,a[j],b[j]);
            reverse(cur_c.begin(),cur_c.end());
            for(auto comp:cur_c) {
                int u=find_par(comp);
                int v=find_par(j);
                if(u!=v) {
                    c[j].push_back(comp);
                    c[comp].push_back(j);
                    //cerr<<"iu"<<endl;
                    unite(u,v);
                    //cerr<<"ou"<<endl;
                }
            }
            int u=find_par(j);
            //cerr<<"ook2."<<i<<endl;
            //assert(tq[u]!=NULL);
            //cerr<<left(tq[u])<<endl;
            update(0,1,2*n,left(tq[u]),1);
        }
        else {
            int j=-ord[i];
            //print_par();
            int u=find_par(j);
            //cerr<<j<<" "<<u<<" "<<pq[u].size()<<endl;
            update(0,1,2*n,left(tq[u]),-1);
            pop_left(tq[u]);
            if(tq[u]!=NULL) update(0,1,2*n,left(tq[u]),1);
        }
        //cerr<<"ok2."<<i<<endl;
    }
    //cerr<<"ok2"<<endl;
    //print_par();
    long long ans=1;
    for(int i=1;i<=n;i++) {
        if(!vis[i]) {
            dfs(i);
            ans=(ans*2)%mod;
        }
    }
    for(int i=1;i<=2*n;i++) {
        if(ord[i]>0) {
            int j=ord[i];
            s[d[j]].push(j);
        }
        else {
            int j=-ord[i];
            if(s[d[j]].top()!=j) {
                printf("0");
                return 0;
            }
            s[d[j]].pop();
        }
    }
    printf("%lld",ans);
    return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:164:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  164 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
port_facility.cpp:165:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  165 |     for(int i=1;i<=n;i++) scanf("%d %d",&a[i],&b[i]);
      |                           ~~~~~^~~~~~~~~~~~~~~~~~~~~

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