Submission #946881

---

Source Code Expand

#include <bits/stdc++.h>

const long long mod=1000000007ll;
const int BS=19;

void bitadd(int *bit,int i,int v)
{
  int p=i+1;
  while(p<1<<BS){
    bit[p]+=v;
    p+=p&-p;
  }
}

int bitsum(int *bit,int i)
{
  int p=i+1,ret=0;
  while(p>0){
    ret+=bit[p];
    p-=p&-p;
  }
  return ret;
}


int main()
{
  int n;
  scanf("%d",&n);
  static int P[500010];
  static bool B[500010]={0};
  int L=0;
  for(int i=0;i<n;i++){
    scanf("%d",P+i);
    if(P[i]==0){
      L++;
    }
    else{
      B[P[i]]=1;
    }
  }
  static int A[500010];
  A[n]=0;
  for(int i=n-1;i>0;i--){
    A[i]=A[i+1]+!B[i+1];
  }
  static int A2[500010];
  A2[1]=0;
  for(int i=2;i<=n;i++){
    A2[i]=A2[i-1]+B[i-1];
  }
  static long long F[500010];
  F[0]=1ll;
  for(int i=1;i<=n;i++){
    F[i]=F[i-1]*i%mod;
  }
  static int bit[1<<19]={0};
  long long ans=0ll;
  long long S0=0ll,S1=0ll;
  for(int i=1;i<=n;i++){
    if(!B[i]){
      S0+=A[i];
    }
    else{
      S1+=A[i];
    }
  }
  int K=0;
  for(int i=0;i<n;i++){
    //printf("%lld %lld\n",S0,S1);
    if(P[i]==0){
      ans+=S0%mod*(L-K-1)%mod*(L>=2?F[L-2]:0ll)%mod*F[n-i-1]%mod;
      ans%=mod;
      ans+=S1%mod*F[L-1]%mod*F[n-i-1]%mod;
      ans%=mod;
      K++;
    }
    else{
      int k=bitsum(bit,P[i]-1);
      ans+=(long long)(A2[P[i]]-k)*F[L]%mod*F[n-i-1]%mod;
      ans%=mod;
      ans+=(long long)(P[i]-1-A2[P[i]])*(L-K)%mod*(L>=1?F[L-1]:0)%mod*F[n-i-1]%mod;
      ans%=mod;
      S1-=A[P[i]];
      bitadd(bit,P[i],1);
    }
    //printf("%lld\n",ans);
  }
  ans+=F[L];
  ans%=mod;
  printf("%lld\n",ans);
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:29:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
                 ^
./Main.cpp:34:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",P+i);
                    ^

Judge Result