Submission #947117

---

Source Code Expand

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<string>
#include<stack>
#include<cstdio>
#include<cmath>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<int,P> P1;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i,x) for(int i=0;i<x;i++)
#define rep1(i,x) for(int i=1;i<=x;i++)
#define rrep(i,x) for(int i=x-1;i>=0;i--)
#define rrep1(i,x) for(int i=x;i>0;i--)
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
#define mp1(a,b,c) P1(a,P(b,c))

const int INF=1000000000;
const int dir_4[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
const int dir_8[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};

const ll M = 1000000007;

ll kaijou[500010];
void init(){
	kaijou[0] = 1;
	rep1(i,500009){
		kaijou[i] = kaijou[i-1] * i;
		kaijou[i] %= M;
	}
}

struct BIT{
	int siz;
	int s[1<<20+1];
	void init(){
		siz = 1<<20;
		rep1(i,siz)s[i] = 0;
	}
	void add(int a){
		while(a <= siz){
			s[a] ++;
			a += a&-a;
		}
	}
	int sum(int a){
		int ret = 0;
		while(a > 0){
			ret += s[a];
			a -= a&-a;
		}
		return ret;
	}
}bit;

int main(){
	init();
	bit.init();
	static int n;
	static int p[500010];
	scanf("%d",&n);
	rep(i,n)scanf("%d",&p[i]);
	
	static int K[500010] = {} , cnt[500010] = {};
	rep1(i,n)cnt[i] = 1;
	rep(i,n){
		K[i] = K[i-1];
		if(p[i] == 0){
			K[i] ++;
		}
		else {
			cnt[p[i]] = 0;
		}
	}
	K[n] = K[n-1];
	rep1(i,500009)cnt[i] += cnt[i-1];
	
	ll c=0,d=0,hoge = 0;
	rep1(i,n){
		if(cnt[i] > cnt[i-1]){
			c += i-1;
			d += cnt[i-1];
		}
	}
	c *= K[n]-1;
	c %= M;
	d %= M;
	
	ll ret = 0;
	rep(i,n){
		if(p[i] != 0){
			ll _ret = 0;
			_ret = kaijou[K[n]]*(p[i]-1-bit.sum(p[i])); _ret %= M;
			_ret += M-( (kaijou[K[n]-1]*K[i])%M*cnt[p[i]] )%M;
			_ret *= kaijou[n-i-1]; _ret %= M;
			ret += _ret; ret %= M;
			bit.add(p[i]);
			hoge += K[n]-cnt[p[i]];
			hoge %= M;
		}
		else {
			ll _ret = c;
			_ret +=M-( (K[n]-1)*hoge )%M;
			_ret +=M-( d*((i==0)?0:K[i-1]) )%M;
			_ret *= kaijou[n-i-1]; _ret %= M;
			_ret *= (K[n] < 2)?0:kaijou[K[n]-2];
			_ret %= M;
			ret += _ret;
			ret %= M;
		}
		/*else {
			ll _ret = 0;
			rep1(j,n){
				if(cnt[j] == cnt[j-1])continue;
				//cout << "__" << i << " " << j << endl;
				ll __ret = 0;
				__ret = kaijou[K[n]-1]*(j-1-bit.sum(j)); __ret %= M;
				//cout << __ret << endl;
				__ret += M-( (kaijou[K[n]-2]*((i==0)?0:K[i-1]))%M*cnt[j-1] )%M;
				//cout << __ret << endl;
				__ret *= kaijou[n-i-1]; __ret %= M;
				//cout << __ret << endl;
				_ret += __ret;
			}
			ret += _ret; ret %= M;
		}*/
		//cout << i << " " << ret << endl;
	}
	
	cout << (ret+kaijou[K[n]])%M << endl;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:76:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:77:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  rep(i,n)scanf("%d",&p[i]);
                           ^

Judge Result