Submission #1318716

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318716		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;
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);}
bool col[N];
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,col[j]=0;
            else col[j]=1;
            Update(R[j],1);
        }
    }
    vector<int>a[2];
    for(int i=1;i<=2*n;i++){
        int j=abs(ev[i]);
        if(ev[i]>0){
            a[col[j]].pb(j);
        }
        else{
            if(a[col[j]].back()!=j)res=0;
            a[col[j]].pop_back();
        }
    }
    printf("%lld\n",res);
    return 0;
}

Compilation message (stderr)

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

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