Submission #1319462

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319462		StefanSebez	Port Facility (JOI17_port_facility)	C++20	78 / 100	1492 ms	1114112 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
const int N=1e6+50,mod=1e9+7,lg=21;
bool test=false;
mt19937 rng(time(0));
int n,ev[2*N],L[N],R[N];
ll Brute(){
    for(int i=1;i<=n;i++)ev[L[i]]=i,ev[R[i]]=-i;
    ll res=0;
    for(int mask=0;mask<1<<n;mask++){
        vector<int>a[2];bool moze=true;
        for(int i=1;i<=2*n;i++){
            int j=abs(ev[i]);
            if(ev[i]>0){
                a[mask>>(j-1)&1].pb(j);
            }
            else{
                if(a[mask>>(j-1)&1].empty()||a[mask>>(j-1)&1].back()!=j){moze=false;break;}
                a[mask>>(j-1)&1].pop_back();
            }
        }
        res+=moze;
    }
    return res;
}
vector<int>E[2*N*lg];
int root1,root2,nc,lc[2*N*lg],rc[2*N*lg];
void Update(int &c1,int C1,int &c2,int C2,int ss,int se,int qind){
    c1=++nc;lc[c1]=lc[C1],rc[c1]=rc[C1];
    c2=++nc;lc[c2]=lc[C2];rc[c2]=rc[C2];
    if(ss==se){
        c2=c1;nc--;
        //printf("c1 %i: [%i %i]\n",c1,ss,se);
        //printf("c2 %i: [%i %i]\n",c2,ss,se);
        return;
    }
    //printf("c1 %i: [%i %i]\n",c1,ss,se);
    //printf("c2 %i: [%i %i]\n",c2,ss,se);
    int mid=ss+se>>1;
    if(qind<=mid)Update(lc[c1],lc[C1],lc[c2],lc[C2],ss,mid,qind);
    else Update(rc[c1],rc[C1],rc[c2],rc[C2],mid+1,se,qind);
    if(lc[c1])E[c1].pb(lc[c1]<<1);
    if(rc[c1])E[c1].pb(rc[c1]<<1);
    if(lc[c2])E[lc[c2]].pb(c2<<1);
    if(rc[c2])E[rc[c2]].pb(c2<<1);
}
void Add(int c1,int c2,int ss,int se,int qs,int qe,int u){
    if(c1==0||c2==0||qs>qe||qe<ss||se<qs)return;
    if(qs<=ss&&se<=qe){
        E[u].pb((c1<<1)^1);
        E[c2].pb((u<<1)^1);
        return;
    }
    int mid=ss+se>>1;
    if(qe<mid+1)Add(lc[c1],lc[c2],ss,mid,qs,qe,u);
    else if(mid<qs)Add(rc[c1],rc[c2],mid+1,se,qs,qe,u);
    else Add(lc[c1],lc[c2],ss,mid,qs,qe,u),Add(rc[c1],rc[c2],mid+1,se,qs,qe,u);
}
bool was[2][2*N*lg];
/*void DFS(int u,bool col=0){
    //cerr<<"vtx: "<<u<<" "<<col<<"\n";
    was[col][u]=true;
    for(auto i:E[u]){
        if(!was[col^(i&1)][i>>1])DFS(i>>1,col^(i&1));
        //if(was[i]&&col^bit!=Col[i]){bip=false;cerr<<u<<"<->"<<i<<"\n";}
        //if(!was[i])bip=min(bip,DFS(i,col^bit));
    }
    //cerr<<u<<"- "<<col<<"\n";
}*/
void BFS(int U,bool col=0){
    vector<int>kju;kju.pb(U<<1);
    while(!kju.empty()){
        int u=kju.back();kju.pop_back();
        was[u&1][u>>1]=true;
        for(auto i:E[u>>1])if(!was[(u&1)^(i&1)][i>>1])kju.pb(((i>>1)<<1)^(u&1)^(i&1));
    }
}
int idx[N],L1[N],R1[N];
ll Solve(){
    for(int i=1;i<=n;i++)ev[L[i]]=i,ev[R[i]]=-i;
    for(int i=1,cnt=-1;i<=2*n;i++){
        int j=abs(ev[i]);
        if(ev[i]>0) L1[j]=cnt;
        else R1[j]=++cnt;
    }
    ll res=1;
    for(int i=1;i<=2*n;i++)if(ev[i]>0){
        int j=ev[i];
        Update(root1,root1,root2,root2,0,n-1,R1[j]);
        idx[j]=nc;
        Add(root1,root2,0,n-1,L1[j]+1,R1[j]-1,nc);
    }
    //for(int i=1;i<=n;i++)printf("leaf %i: %i\n",i,idx[i]);
    //for(int i=1;i<=nc;i++){printf("%i: ",i);for(auto [j,bit]:E[i])printf("[%i %i] ",j,bit?1:0);printf("\n");}
    for(int i=1;i<=n;i++)if(!was[0][idx[i]]&&!was[1][idx[i]]){
        BFS(idx[i]);
        res=(res<<1)%mod;
    }
    for(int i=1;i<=n;i++)if(was[0][idx[i]]&&was[1][idx[i]])res=0;
    for(int i=0;i<=nc;i++){
        was[0][i]=was[1][i]=lc[i]=rc[i]=0;
        idx[i]=L1[i]=R1[i]=0;
        E[i].clear();
    }
    root1=root2=nc=0;
    return res;
}
int main(){
    if(!test){
        scanf("%i",&n);
        for(int i=1;i<=n;i++){
            int x,y;scanf("%i%i",&x,&y);
            L[i]=x,R[i]=y;
        }
        ll res=Solve();
        printf("%lld\n",res);
    }
    else{
        int CT=0;
        while(++CT){
            if(CT%100==1)cerr<<"radi\n";
            n=10;
            vector<int>temp(2*n);iota(temp.begin(),temp.end(),1);
            shuffle(temp.begin(),temp.end(),rng);
            for(int i=0,j=1;i<2*n;i+=2,j++){
                L[j]=temp[i],R[j]=temp[i+1];
                if(L[j]>R[j])swap(L[j],R[j]);
            }
            ll x=Brute(),y=Solve();
            if(x!=y){
                printf("%i\n",n);
                for(int i=1;i<=n;i++)printf("%i %i\n",L[i],R[i]);
                printf("\n%lld %lld\n",x,y);
                return 0;
            }
        }
    }
    return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:114:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |         scanf("%i",&n);
      |         ~~~~~^~~~~~~~~
port_facility.cpp:116:26: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |             int x,y;scanf("%i%i",&x,&y);
      |                     ~~~~~^~~~~~~~~~~~~~

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