Submission #329853

#	Time	Username	Problem	Language	Result	Execution time	Memory
329853		milisav	Port Facility (JOI17_port_facility)	C++14	100 / 100	4654 ms	354140 KiB

port_facility

#include<bits/stdc++.h>
#define maxn 2500000
using namespace std;
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;
set<int> st[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) {
    if(st[u].size()>st[v].size()) swap(u,v);
    par[u]=v;
    st[v].insert(st[u].begin(),st[u].end());
}
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;
        st[i].insert(b[i]);
    }
    //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]);
            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);
                    unite(u,v);
                }
            }
            int u=find_par(j);
            update(0,1,2*n,(*st[u].begin()),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,(*st[u].begin()),-1);
            st[u].erase(st[u].begin());
            if(!st[u].empty()) update(0,1,2*n,(*st[u].begin()),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:74:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   74 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
port_facility.cpp:75:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   75 |     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