Submission #1318713

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318713		StefanSebez	Port Facility (JOI17_port_facility)	C++20	0 / 100	0 ms	332 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;
int n,ev[2*N];
int L[N],R[N];
ll res=1;
vector<int>a,b;
set<int>A,B;
int T[2*N];
void Update(int i,int x){for(;i<=2*N;i+=i&-i)T[i]+=x;}
int Get(int i){int x=0;for(;i>=1;i-=i&-i)x+=T[i];return x;}
int Get(int l,int r){return Get(r)-Get(l-1);}
int main(){
    scanf("%i",&n);
    for(int i=1;i<=n;i++){
        int x,y;scanf("%i%i",&x,&y);
        ev[x]=i,ev[y]=-i;
        L[i]=x,R[i]=y;
    }
    for(int i=1;i<=2*n;i++){
        int j=abs(ev[i]);
        if(ev[i]>0){
            if(Get(L[j],R[j])==0)res=(res<<1)%mod;
            Update(R[j],1);
        }
    }
    for(int i=1;i<=2*n;i++){
        int j=abs(ev[i]);
        if(ev[i]>0){
            int bul=0;
            if(A.empty()||*A.begin()>R[j]){
                a.pb(j),A.insert(R[j]);
                bul++;
            }
            if(B.empty()||*B.begin()>R[j]){
                if(bul==0)b.pb(j),B.insert(R[j]);
                bul++;
            }
            if(bul==0){res=0;break;}
        }
        else{
            if(a.back()==j){
                a.pop_back();
                A.erase(R[j]);
            }
            else if(b.back()==j){
                b.pop_back();
                B.erase(R[j]);
            }
            else{res=0;break;}
        }
    }
    printf("%lld\n",res);
    return 0;
}

Compilation message (stderr)

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

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